约数之和（数论）

前言

失恋了跑过来写这题，想当年这题咕了好久，现在分分钟切了。

ACwing题目地址

Solution

通过唯一分解定理：

\[A=p^{\alpha_1}_1*p^{\alpha_2}_2*...*p^{\alpha_n}_n\]

所以：

\[A^B=p^{\alpha_1*B}_1*p^{\alpha_2*B}_2*...*p^{\alpha_n*B}_n\]

~~通过自己研究研究可以知道的两个定理~~：

1.约数个数定理：

\[Num(A)=(1+\alpha_1)*(1+\alpha_2)*...*(1+\alpha_n)\]

解释：从每一个质数里面任选一个次幂（选择范围 \([0,\alpha_i]\)），与其他质数相组合就是一个约数，所以约数个数就是上面这个式子。

2.约数和定理：

\[Sum(A)=(1+p_1^1+p_1^2+...+p_1^{\alpha_1})*(1+p_2^1+p_2^2+...+p_2^{\alpha_2})*...*(1+p_n^1+p_n^2+...+p_n^{\alpha_n})\]

解释：每个括号里面就是每一个质数的任一个次幂（次幂范围 \([0,\alpha_i]\)）之和，如果把括号拆开，就是每个括号里面选一个数乘起来，再把所有选择加起来。每个括号选一个数乘起来，不正对应每一个约数的值吗？所以约数和就是上面这个式子。

上面这个式子有 ~~亿点点~~ 难看，我们把它写简洁一点就是：

\[Sum(A)=\prod_{i=1}^n (\sum_{j=0}^{\alpha_i}p_i^j)\]

回到题目，在这个题目里的 约数和 就是如下式子：

\[Ans=\prod_{i=1}^n (\sum_{j=0}^{\alpha_i*B}p_i^j)\]

暴力计算复杂度 \(O(n^2)\)，还要带上个质因数分解的复杂度。本题数据 \(n<=5*10^7\)，因此要想办法优化。

发现 \(\sum_{j=0}^{\alpha_i*B}p_i^j\) 不就是一个 等比数列求和 吗？等比数列求和公式

注意在 模意义 下，除一个数要用乘它的逆元代替，模数 \(9901\) 是一个素数，可以用 费马小定理 直接求得逆元。（~~这题目要用的东西还挺多的~~）

所以最后分别求出 \(n\) 个等比数列求和，全部乘起来就是答案。每个等比数列 \(a_0=1,q=p_i\) （\(q\) 是公比）。这样我们就可以求出整个题目的解了。

求一次乘法逆元的复杂度是 \(O(\log MOD)\)，因为 \(MOD\) 较小，可以忽略记为常数；求一次快速幂的复杂度是 \(O(\log N)\) 这个应该小于 \(32\)。所以总复杂度应该是 \(O(9 * \log n)\) (大雾（有一个著名的定理 \(n<=10^9\) 分解出来的质数不超过9个）

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
#define MOD 9901
#define int long long
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
int A,B;
vector<pair<int,int> > p;
int Pow(int x,int y) {  //9901是质数，直接上费马小 
    int res = 1, base = x;
    while(y) {
        if(y&1) res = (res*base)%MOD; base = (base*base)%MOD; y >>= 1;
    }
    return res;
}
signed main()
{
    A = read(), B = read();
    if(A == 0) {
        puts("0"); return 0;
    }
    while(A > 1) {
        for(int i=2;i<=A;++i) {
            if(A%i == 0) {
                int num = 0;
                while(A%i == 0) A /= i, ++num;
                p.push_back(make_pair(i,num));
                break;
            }
        }
    }
    int ans = 1, inv, S;
    for(int i=0;i<p.size();++i) {
        inv = Pow(p[i].first-1+MOD%MOD,MOD-2);
        S = (Pow(p[i].first, p[i].second*B+1)-1+MOD)%MOD;
        S = (S*inv)%MOD;
        ans = (ans*S)%MOD;
    }
    printf("%lld\n",ans);
    return 0;
}