约数之和(分解质因子&&分治递归求约数之和)

假设现在有两个自然数A和B，S是AB的所有约数之和。

请你求出S mod 9901的值是多少。

输入格式

在一行中输入用空格隔开的两个整数A和B。

输出格式

输出一个整数，代表S mod 9901的值。

数据范围

0≤A,B≤5×107

输入样例：

2 3

输出样例：

15

注意: A和B不会同时为0。

思路：可以将a用所有质因子的乘积表示，即：

a=p1^k1*p2^k2*...*pn^kn  (pi为a的第i个质因子，ki为第i个质因子的个数) 

a的所有约数可由这些质因子组合而成，所以每个质因子都可能有0~k（k+1）种次幂，所以按照组合的乘法原理乘起来一共可以组合成（k1+1）*(k2+1)*...*(kn+1)种不同的约数，每一个约数都是选择每个质因子的k种次幂中的一种，然后乘起来所得，所以约数之和即为：（p1^0+p1^1+.. +p1^k1）*(p2^0+p2^1+...+p2^k2)*...*(pn^0+pn^1+...pn^kn)，从每个括号里选一项然后乘起来便组成一个约数，然后把上式乘开，就是所有约数之和的形式了。

所以，总结一下：

对于a=p1^k1*p2^k2*...*pn^kn  (pi为a的第i个质因子，ki为第i个质因子的个数) ：

a的约数个数为：（k1+1）*(k2+1)*...*(kn+1)

a的约数之和为：（p1^0+p1^1+.. +p1^k1）*(p2^0+p2^1+...+p2^k2)*...*(pn^0+pn^1+...pn^kn)

用sum(p,k)表示个数为k的质因子p的那一括号的多项式（如：sum（p1,k1）=（p1^0+p1^1+.. +p1^k1））,默认k为奇数，

sum（p,k）   =（p^0+p^1+.. +p^k）

                       =（p^0+p^1+...+p^(k/2)）+(p^(k/2+1)+...+p^(k))

                       =（p^0+p^1+...+p^(k/2)）+（p^(k/2+1)*(p^0+p^1+...+p^(k/2))）(因为k/2为向下取整，所以(k/2+1)+k/2=k)

                       =  (1+p^(k/2+1))*(p^0+p^1+...p^(k/2))

                       =  (1+p^(k/2+1))*sum(p,k/2) (这样就利用分治将问题规模缩小了一半)

完整代码：

#include <iostream>
const int mod=9901;
using namespace std;
int a,b;

int qmi(int x,int y)//快速幂
{
    x%=mod;
    int res=1;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}

int sum(int p,int k)
{
    if(k==0) return 1;//p^0=1
    if(k%2==0) return (p%mod*sum(p,k-1)+1)%mod;//k为偶数，则算后边k-1项p*(p^0+...+p^k-1)=(p^1+..+p^k)，然后再加上p^0=1
    return ((1+qmi(p,k/2+1))*sum(p,k/2))%mod;//k为奇数，则直接代入公式
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>a>>b;
    int ans=1;
    for(int i=2;i<=a;i++){//分解质因子模板（将a分解成所有质因子之积的形式）
        int cnt=0;//cnt记录当前质因子个数
        while(a%i==0){//i为a的一个质因子
            a/=i;
            cnt++;
        }
        if(cnt) ans=ans*sum(i,cnt*b)%mod;
    }
    if(!a) ans=0;
    cout<<ans<<endl;
    return 0;
}