当前位置：首页 > article >正文

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

article 2024/11/14 15:37:17

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 个。