摘要
Title: 97. 约数之和
Tag: 数论、约数
Memory Limit: 64 MB
Time Limit: 1000 ms

97. 约数之和

题意

假设现在有两个自然数 A和 B，S是 A^B的所有约数之和。
请你求出 S mod 9901的值是多少。
思路

$A^B$ 的约数之和为： $sum_{A^B} = (1 +p_1 + p_1 ^ 2 + ... + p_1^{B×a_1}) × (1 +p_2 + p_2 ^ 2 + ... + p_2^{B×a_2}) × ...$
为什么最高项是 $B×a$ 呢，最高项代表 $p$ 这个质因子的个数，一开始 $A$ 有 $x$ 个 $p$ ，那么 $A^3=A×A×A$ 就有 $3x$ 个 $p$
- 做法一：等比数列求和 + 快速幂
  
  所以，对于每个质因子，根据等比数列求和公式 $(1 +p + p ^ 2 + ... + p^{B×a}) = \frac{p^{B×a+1}-1}{p-1}$
  那么，对 $A$ 进行质因子分解
  - $p^{B×a+1}$ 用快速幂求
  - $\frac{1}{p-1}$ $\frac{1}{p - 1}$ 用费马小定理求逆元，但必须保证 $p-1$ $p - 1$ 与 $MOD$ $M O D$ 互质
    - 若 $p-1$ 与 $MOD$ 互质，正常求即可
    - 若 $p-1$ 与 $MOD$ 不互质，我们无法求逆元，就换种思路求表达式。因为 $p \% MOD = 1$ ， $(1 +p + p ^ 2 + ... + p^{B×a}) \% MOD= 1 + B×a ×1 = 1 + B×a$ ，所以直接返回 $1 + B×a$ 即可
  复杂度 $O(\sqrt{n}log(n))$
- 做法二：分治 + 快速幂
  定义 $sum(p, k) = (1 +p + p ^ 2 + ... + p^{k})$ ，共 $k +1$ 项
  - 当 $k$ 为奇数时，项数为偶数，以下默认 $\frac{k}{2} =\lfloor \frac{k}{2} \rfloor$
    原式 $=(p^0+p^1+...+p^{\frac{k}{2}}) +(p^{\frac{k}{2} +1}+...+p^k) = (p^0+p^1+...+p^{\frac{k}{2}}) + p^{\frac{k}{2} +1} × (p^0+p^1+...+p^{\frac{k}{2}}) = (1 + p^{\frac{k}{2} +1} ) × sum(p, \frac{k}{2})$
  - 当 $k$ 为偶数时，转化为奇数情况， $sum(p,k) = sum(p ,k - 1) + p^k$
  复杂度 $O(\sqrt{n}log(n)log(n))$
- 超时做法三：递推
  求 $(p^0+p^1+...+p^k)$ ，可用递推式，ans = ans * p + 1，但此做法会超时

代码

做法一

/*
 * @Author: NEFU AB-IN
 * @Date: 2023-02-18 11:22:46
 * @FilePath: \Acwing\97\97.cpp
 * @LastEditTime: 2023-02-18 23:11:41
 */
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 9901;

int quickmod(int a, int b)
{
    a %= MOD;
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b = b >> 1;
    }
    return res % MOD;
}

signed main()
{
    IOS;
    int a, b;
    cin >> a >> b;
    if (!a)
    {
        cout << 0;
        return 0;
    }
    // 质因子分解
    unordered_map<int, int> mp;
    for (int i = 2; i <= a / i; ++i)
    {
        while (a % i == 0)
        {
            mp[i]++;
            a /= i;
        }
    }
    if (a > 1)
        mp[a]++;
    int ans = 1;

    auto f = [&](int p, int n) {
        if ((p - 1) % MOD == 0)
            return n + 1;
        int pp = quickmod(p, n + 1);
        int ny = quickmod(p - 1, MOD - 2);
        return (pp - 1 + MOD) * ny % MOD;
    };

    for (auto [x, cnt] : mp)
    {
        ans = ans * f(x, cnt * b) % MOD;
    }
    cout << ans;
    return 0;
}

做法二

/*
 * @Author: NEFU AB-IN
 * @Date: 2023-02-18 12:21:32
 * @FilePath: \Acwing\97\97.1.cpp
 * @LastEditTime: 2023-02-19 11:36:53
 */
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 9901;

int quickmod(int a, int b)
{
    a %= MOD;
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b = b >> 1;
    }
    return res % MOD;
}

int sum(int p, int k)
{
    if (k == 0)
        return 1;
    if (k % 2 == 0)
        return sum(p, k - 1) % MOD + quickmod(p, k) % MOD;
    return sum(p, k / 2) % MOD * (1 + quickmod(p, k / 2 + 1)) % MOD;
}

int main()
{
    IOS;
    int a, b;
    cin >> a >> b;
    if (!a)
    {
        cout << 0;
        return 0;
    }
    // 质因子分解
    unordered_map<int, int> mp;
    for (int i = 2; i <= a / i; ++i)
    {
        while (a % i == 0)
        {
            mp[i]++;
            a /= i;
        }
    }
    if (a > 1)
        mp[a]++;
    int ans = 1;

    for (auto [x, cnt] : mp)
    {
        ans = ans * sum(x, cnt * b) % MOD;
    }
    cout << ans;
    return 0;
}

97. 约数之和

题意

思路

代码