本文共 2955 字，大约阅读时间需要 9 分钟。

数论是数学中的一个重要分支，它研究数的性质及其在各种数学问题中的应用。今天我们将探讨数论中的两个核心问题：因子和与因子个数，并通过具体代码示例来理解和解决这些问题。

求因子和

因子和是将一个数分解为素因数的所有不同组合的乘积之和。例如，对于一个数n，我们可以将其表示为多个素数的幂次方的乘积，然后计算所有可能的组合乘积的总和。具体来说，假设n可以分解为以下形式：

n = p₁^a₁ × p₂^a₂ × … × p_k^a_k

那么，因子和就是所有可能的因子的乘积之和。例如，对于n=12，其素因数分解为2^2 × 3^1，因子和为：

(1 + 2 + 4) × (1 + 3) = 7 × 4 = 28

以下是实现因子和的代码示例：

#include 
   
    
#define ll long long
const int N = 1e6 + 5;
int cnt, prime[N], pre[N];
bool flag[N];
using namespace std;
void init() {
    memset(flag, 1, sizeof(flag));
    flag[1] = false;
    for (int i = 2; i <= N; ++i) {
        if (flag[i]) {
            prime[++cnt] = i;
            pre[i] = cnt;
        }
        for (int j = 1; j <= cnt && prime[j] * i <= N; ++j) {
            flag[prime[j] * i] = false;
            if (i % prime[j] == 0) break;
        }
    }
}
ll get_yin_zi_sum(ll n) {
    ll ans = 1;
    for (int i = 1; (ll)prime[i] * prime[i] <= n; ++i) {
        if (n % prime[i] == 0) {
            ll jet = 1, sum = 1;
            while (n % prime[i] == 0) {
                jet *= prime[i];
                sum += jet;
                n /= prime[i];
            }
            ans *= sum;
        }
    }
    if (n > 1) {
        ans *= (n + 1);
    }
    return ans;
}
void solve() {
    ll x;
    scanf("%lld", &x);
    printf("%lld\n", get_yin_zi_sum(x));
}
int main() {
    init();
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    return 0;
}
   

求因子个数

因子个数是指一个数的所有因数的数量，包括1和它本身。例如，对于n=6，其素因数分解为2^1 × 3^1，因子个数为：

(1 + 1) × (1 + 1) = 2 × 2 = 4

以下是实现因子个数的代码示例：

#include 
   
    
#define ll long long
const int N = 1e6 + 5;
int cnt, prime[N], pre[N];
bool flag[N];
using namespace std;
void init() {
    memset(flag, 1, sizeof(flag));
    flag[1] = false;
    for (int i = 2; i <= N; ++i) {
        if (flag[i]) {
            prime[++cnt] = i;
            pre[i] = cnt;
        }
        for (int j = 1; j <= cnt && prime[j] * i <= N; ++j) {
            flag[prime[j] * i] = false;
            if (i % prime[j] == 0) break;
        }
    }
}
ll get_yin_zi_num(ll n) {
    ll ans = 1;
    for (int i = 1; (ll)prime[i] * prime[i] <= n; ++i) {
        if (n % prime[i] == 0) {
            ll cnt = 0;
            while (n % prime[i] == 0) {
                cnt++;
                n /= prime[i];
            }
            ans *= (1 + cnt);
        }
    }
    if (n > 1) {
        ans *= 2;
    }
    return ans;
}
void solve() {
    ll x;
    scanf("%lld", &x);
    printf("%lld\n", get_yin_zi_num(x - 1) % mod);
}
int main() {
    init();
    scanf("%d%d", &t, &mod);
    while (t--) {
        solve();
    }
    return 0;
}
   

代码解释

通过上述代码，我们可以快速计算出任意一个正整数的因子和与因子个数。这些建议的算法基于线性筛法，能够在较短的时间内处理较大的数。