约数计算与应用

1. 使用试除法求解约数

试除法是一种基础但有效的求解正整数约数的方法。对于给定的一系列正整数，本节将展示如何利用试除法找出每个数的所有约数，并按升序排列输出。

问题描述：给定 n 个正整数 ai，任务是输出每个整数 ai 的所有约数，按从小到大顺序。

输入格式：首行输入一个整数 n，表示正整数的数量。随后 n 行，每行输入一个整数 ai。

输出格式：输出共 n 行，每行对应输入的一个整数 ai 的所有约数，以空格分隔。

数据限制：1 ≤ n ≤ 100, 2 ≤ ai ≤ 2 × 10^9

示例代码：

#include
#include
#include
using namespace std;

vector findDivisors(int n) {
    vector divisors;
    for(int i = 1; i <= n / i; i++) {
        if(n % i == 0) {
            divisors.push_back(i);
            if(i != n / i) divisors.push_back(n / i);
        }
    }
    sort(divisors.begin(), divisors.end());
    return divisors;
}

int main() {
    int n;
    cin >> n;
    while(n--) {
        int x;
        cin >> x;
        auto divisors = findDivisors(x);
        for(auto d : divisors) cout <        cout <    }
    return 0;
}

2. 计算约数的个数

此部分探讨了如何计算一组正整数乘积的约数个数，并对结果取模 10^9 + 7。

输入格式：与上一节类似，首先输入整数 n 表示正整数的数量，然后输入 n 个正整数。

输出格式：输出一个整数，表示所有输入整数乘积的约数个数，结果需要对 10^9 + 7 取模。

示例代码：

#include
#include
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    unordered_map primeFactors;
    while(n--) {
        int x;
        cin >> x;
        for(int i = 2; i <= x / i; i++) {
            while(x % i == 0) {
                primeFactors[i]++;
                x /= i;
            }
        }
        if(x > 1) primeFactors[x]++;
    }
    long long answer = 1;
    for(auto& factor : primeFactors) {
        answer = answer * (factor.second + 1) % MOD;
    }
    cout <    return 0;
}

3. 求解约数之和

本节介绍了一种计算一组正整数乘积的约数之和的方法，同样地，最终结果需要对 10^9 + 7 取模。

示例代码：

#include
#include
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    unordered_map primeFactors;
    while(n--) {
        int x;
        cin >> x;
        for(int i = 2; i <= x / i; i++) {
            while(x % i == 0) {
                primeFactors[i]++;
                x /= i;
            }
        }
        if(x > 1) primeFactors[x]++;
    }
    long long answer = 1;
    for(auto& factor : primeFactors) {
        long long base = factor.first, exp = factor.second;
        long long sum = 1;
        while(exp--) sum = (sum * base + 1) % MOD;
        answer = answer * sum % MOD;
    }
    cout <    return 0;
}

4. 应用欧几里得算法求最大公约数

最后一部分讨论了如何使用欧几里得算法来寻找两个正整数的最大公约数。这种方法不仅高效而且易于实现。

输入格式：首先输入一个整数 n 表示正整数对的数量，接着输入 n 对正整数。

输出格式：输出 n 行，每行对应一对输入正整数的最大公约数。

示例代码：

#include
using namespace std;

int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    int n;
    cin >> n;
    while(n--) {
        int a, b;
        cin >> a >> b;
        cout <    }
    return 0;
}