Acwing97题：约数之和

求每个数字的约数和约数个数,假设约数为$p$，约数最多$k$个

那么我们要用一种排列组合的思想去做（细节不阐述了）

$p^0+p^1+p^2+p^3+…+p^k$

对每个数的约数都如此操作，然后乘到最后的答案里去

问题在于对每个$p$都做一遍$O(k)$的算法很浪费时间

所以我们用分治的思想去简化

假设k为奇数

公式可以转化为$sum(p,k)=(1+p^\frac{k}{2})*sum(p,\frac{k-1}{2})$

如果k为偶数的话，我们可以投机取巧地将它变成奇数

$sum(p,k)=sum(p,k-1)+p^k$

最后所有的$p^\frac{k}{2}$或$p^k$用取模快速幂做就可以了

复杂度就被下降为了$O(logk)$的级别

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

int qmi(int a,int b,int p){
    int ans=1;
    while(b){
        if(b&1) ans=ans*1ll*a%p;
        b>>=1;
        a=a*1ll*a%p;
    }
    return ans%p;
}

int sum(int p,int k){
    if(k==0) return 1;
    else if(k&1) return sum(p,(k-1)/2)*1ll*(qmi(p,(k+1)/2,mod)+1)%mod;
    else return (sum(p,k/2-1)*1ll*(qmi(p,k/2,mod)+1)%mod+qmi(p,k,mod))%mod;
}

int main(){
    int a,b,ans=1;
    scanf("%d%d",&a,&b);
    for(int i=2;i<=a/i;i++){
        if(a%i==0){
            int s=0;
            while(a%i==0) a/=i,s++;
            ans=ans*1ll*sum(i,s*b)%mod;
        }
    }
    if(a>1) ans=ans*1ll*sum(a,b)%mod;
    if(a==0) ans=0;
    printf("%d\n",ans);
    return 0;
}