P1036 [NOIP2002 普及组] 选数
题目描述
[NOIP2002 普及组] 选数 - 洛谷
运行代码
#include <stdio.h>
int n, k, a[25], t;
int ss(int b) {
int i;
if (b < 2)
return 0;
for (i = 2; i * i <= b; i++)
if (b % i == 0)
return 0;
return 1;
}
void dfs(int num, int sum, int j) {
int i;
if (num == k) {
if (ss(sum))
t++;
return;
}
for (i = j; i < n; i++)
dfs(num + 1, sum + a[i], i + 1);
return;
}
int main() {
int i;
scanf("%d %d", &n, &k);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
dfs(0, 0, 0);
printf("%d", t);
return 0;
}改进后
- 将判断一个数是否为质数的函数
ss改名为isPrime，使其功能更清晰易懂。 - 在
dfs函数中，将原本在全局变量中的k和数组a以及用于计数的t作为参数传递进去，这样可以使函数的独立性更强，不需要依赖全局变量，降低了代码的耦合度。 - 在
isPrime函数中，使用sqrt(b)来代替i * i <= b，在判断一个数是否为质数时，只需要遍历到该数的平方根即可，这样可以稍微提高一些效率。
#include <stdio.h>
#include <math.h>
// 判断一个数是否为质数
int isPrime(int b) {
if (b < 2) return 0;
for (int i = 2; i <= sqrt(b); i++) {
if (b % i == 0) return 0;
}
return 1;
}
// 深度优先搜索函数
void dfs(int num, int sum, int j, int k, int *a, int *t) {
if (num == k) {
if (isPrime(sum)) (*t)++;
return;
}
for (int i = j; i < n; i++) {
dfs(num + 1, sum + a[i], i + 1, k, a, t);
}
}
int main() {
int n, k, a[25], t = 0;
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
dfs(0, 0, 0, k, a, &t);
printf("%d", t);
return 0;
}代码思路
这段代码的主要目的是从给定的一组整数中选取 k 个整数，将它们相加，然后判断相加的和是否为质数，统计满足条件的组合数量。
-
数据读取与初始化：
- 在
main函数中，首先通过scanf读取两个整数n和k，其中n表示给定的整数数组a的长度，k表示要从数组中选取的整数个数。 - 接着通过循环使用
scanf读取数组a中的每一个元素。 - 同时初始化一个变量
t为0，用于统计满足条件（即选取的k个整数相加和为质数）的组合数量。
- 在
-
深度优先搜索（DFS）实现组合选取：
dfs函数用于实现深度优先搜索来找出所有可能的k个整数的组合。它接受几个参数：t：用于统计满足条件的组合数量（通过指针传递，以便在函数内部修改其值）。a：给定的整数数组（从main函数传递过来）。k：要选取的整数个数（从main函数传递过来）。j：表示下一个可供选取的整数在数组a中的索引。sum：表示当前选取的整数相加的和。num：表示当前已经选取的整数个数。- 在
dfs函数内部：- 当
num等于k时，说明已经选取了k个整数，此时调用isPrime函数判断sum是否为质数，如果是，则将t的值加1，然后返回。 - 如果
num不等于k，则通过循环从索引j开始遍历数组a，对于每一个元素a[i]，递归调用dfs函数，将num加1（表示又选取了一个整数），sum加a[i]（更新选取的整数相加的和），i + 1（更新下一个可供选取的整数的索引）。
- 当
-
判断质数函数：
isPrime函数用于判断一个数是否为质数。它接受一个整数b作为参数。- 如果
b小于2，则直接返回0，因为小于2的数不是质数。 - 然后通过循环从
2开始遍历到sqrt(b)，如果在这个范围内发现b能被某个数整除（即b % i == 0），则返回0，说明b不是质数；如果遍历完整个范围都没有发现这样的数，则返回1，说明b是质数。
-
结果输出：最后，在
main函数中，通过printf输出统计得到的满足条件的组合数量t。
综上所述，该代码通过深度优先搜索遍历所有可能的 k 个整数的组合，然后判断每个组合的和是否为质数，从而统计出满足条件的组合数量。
P1045 [NOIP2003 普及组] 麦森数（高精度快速幂）
题目描述
[NOIP2003 普及组] 麦森数 - 洛谷
运行代码
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
const int N = 500;
typedef vector<int> VI;
VI a(N), res(N);
int p;
VI mul(VI& a, VI& b) {
VI t(N * 2);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
t[i + j] += a[i] * b[j];
t[i + j + 1] += t[i + j] / 10;
t[i + j] %= 10;
}
return t;
}
void quick_pow(int p) {
res[0] = 1, a[0] = 2;
while (p) {
if (p & 1)
res = mul(res, a);
a = mul(a, a);
p >>= 1;
}
res[0]--;
}
int main() {
cin >> p;
printf("%d\n", int(p * log10(2)) + 1);
quick_pow(p);
for (int i = 0, k = 499; i < 10; i++) {
for (int j = 0; j < 50; j++, k--)
printf("%d", res[k]);
puts(" ");
}
return 0;
}改进后
- 在
mul函数中，将结果向量t的初始化大小改为根据输入向量a和b的大小动态确定，更加灵活且避免了可能的空间浪费。同时，在函数结尾添加了去除前导0的操作，使结果更加规范。 - 在
quick_pow函数中，将res和a的初始化放在函数内部，使函数更加独立，不需要依赖全局变量。并且将res作为参数传入，这样可以在函数内部直接修改其值，而不是像原来那样通过全局变量来操作。 - 在
main函数中，使用cout代替printf，使代码风格更加统一（因为前面已经使用了iostream库）。同时，在输出结果时，对超出向量范围的情况进行了处理，即当索引小于0时输出0，保证了输出的完整性。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 高精度乘法函数，计算两个大整数向量的乘积
vector<int> mul(const vector<int>& a, const vector<int>& b) {
vector<int> t(a.size() + b.size(), 0);
for (size_t i = 0; i < a.size(); ++i) {
for (size_t j = 0; j < b.size(); ++j) {
t[i + j] += a[i] * b[j];
t[i + j + 1] += t[i + j] / 10;
t[i + j] %= 10;
}
}
// 去除前导0
while (t.size() > 1 && t.back() == 0) t.pop_back();
return t;
}
// 快速幂函数，用于计算2的p次方
void quick_pow(int p, vector<int>& res) {
res = {1};
vector<int> a = {2};
while (p) {
if (p & 1) res = mul(res, a);
a = mul(a, a);
p >>= 1;
}
res[0]--;
}
int main() {
int p;
cin >> p;
// 先输出结果的位数
cout << static_cast<int>(p * log10(2)) + 1 << endl;
vector<int> res;
quick_pow(p, res);
// 输出结果，每50个数字为一行
for (int i = 0, k = res.size() - 1; i < 10; ++i) {
for (int j = 0; j < 50; ++j, k--) {
if (k >= 0) cout << res[k];
else cout << 0;
}
cout << endl;
}
return 0;
}代码思路
这段代码主要实现了两个功能：一是计算并输出 2 的 p 次方减 1 的结果（以高精度整数的形式），二是先输出这个结果的位数。
-
高精度乘法函数
mul：- 目的是实现两个大整数（以
vector<int>形式存储，每个元素代表整数的一位）的乘法运算。 - 首先创建一个大小为
a.size() + b.size()的结果向量t，初始值都为0。 - 然后通过两层嵌套的循环遍历两个输入向量
a和b的每一位。对于每一对位a[i]和b[j]，将它们的乘积加到t[i + j]上。接着处理进位，将t[i + j]除以10的商加到t[i + j + 1]上，同时将t[i + j]除以10的余数保留在t[i + j]上。 - 最后，通过循环去除结果向量
t中的前导0，得到规范的乘法结果并返回。
- 目的是实现两个大整数（以
-
快速幂函数
quick_pow：- 基于快速幂算法来计算
2的p次方。快速幂算法的基本思想是通过不断地将指数减半，同时根据指数的奇偶性来决定是否将当前的中间结果与底数相乘，从而减少乘法运算的次数，提高计算效率。 - 首先初始化
res为只包含一个元素1的向量，表示2的0次方结果；初始化a为只包含一个元素2的向量，表示底数。 - 然后在循环中，当
p不为0时：- 如果
p是奇数（即p & 1为真），则将当前的中间结果res与底数a相乘，更新res的值。 - 然后将底数
a自身相乘，更新a的值。 - 最后将
p除以2（通过p >>= 1实现），继续下一轮循环。
- 如果
- 循环结束后，将
res的第一个元素减1，得到2的p次方减1的结果。
- 基于快速幂算法来计算
-
主函数
main：- 首先通过
cin读取输入的整数p。 - 接着计算并输出
2的p次方减1的结果的位数。根据对数的性质，一个数N的位数可以通过log10(N)来估算，对于2的p次方，其位数大约为p * log10(2)，再加上1是因为可能存在进位情况，所以通过cout输出int(p * log10(2)) + 1。 - 然后调用
quick_pow函数计算2的p次方减1的结果，并将结果存储在res向量中。 - 最后，通过两层嵌套的循环将
res中的结果以每50个数字为一行的方式输出。在循环中，先从res的末尾开始向前遍历，对于每一行，输出50个数字，如果遇到索引小于0的情况（即已经遍历完所有数字），则输出0，保证每行输出的数字数量固定为50个。
- 首先通过
综上所述，该代码通过高精度乘法和快速幂算法实现了对 2 的 p 次方减 1 的计算和输出，同时也给出了结果的位数估算。
