洛谷每日一题——P1036 [NOIP2002 普及组] 选数、P1045 [NOIP2003 普及组] 麦森数（高精度快速幂）

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 个整数，将它们相加，然后判断相加的和是否为质数，统计满足条件的组合数量。

1. 数据读取与初始化：

   • 在 main 函数中，首先通过 scanf 读取两个整数 n 和 k，其中 n 表示给定的整数数组 a 的长度，k 表示要从数组中选取的整数个数。
   • 接着通过循环使用 scanf 读取数组 a 中的每一个元素。
   • 同时初始化一个变量 t 为 0，用于统计满足条件（即选取的 k 个整数相加和为质数）的组合数量。

2. 深度优先搜索（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（更新下一个可供选取的整数的索引）。

3. 判断质数函数：

   • isPrime 函数用于判断一个数是否为质数。它接受一个整数 b 作为参数。
   • 如果 b 小于 2，则直接返回 0，因为小于 2 的数不是质数。
   • 然后通过循环从 2 开始遍历到 sqrt(b)，如果在这个范围内发现 b 能被某个数整除（即 b % i == 0），则返回 0，说明 b 不是质数；如果遍历完整个范围都没有发现这样的数，则返回 1，说明 b 是质数。

4. 结果输出：最后，在 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;}}// 去除前导0while (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 的结果（以高精度整数的形式），二是先输出这个结果的位数。

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，得到规范的乘法结果并返回。

2. 快速幂函数 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 的结果。

3. 主函数 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 的计算和输出，同时也给出了结果的位数估算。