啥都别看，只是求
\(a^b\)所有的因数的和
思路：
真没想到！
其实我们可以先将\(a^b\)分解成质因数的
因为\(a^b\)的因数肯定是\(a^b\)的质因数在一定的条件下相乘而成的
然后组合一下
正解！！！
h^ovny：走开！别误导别人！
来一波公式：
\(a=\Pi^n_{i=1}p[i]^{c[i]}\)
\(a^b=\Pi^n_{i=1}p[i]^{c[i]*b}\)
所有因数的和：
\(Ans=\Pi_{i=1}^n\Sigma^{k[i]}_{j=0}p[i]^j\)
\(\Pi\) ：读作Pi，是\(\pi\)的大写，表示累乘
\(\Sigma\) ：读作Sigma，是\(\sigma\)的大写，表示累加
现在的问题就变成了如何求：
\(\Sigma_{j=0}^{k[i]}\)
展开来写乘：
\((1+p+p^2+p^3+…+p^k)\)
用分治法的思想求解
当k为奇数时：
\(f(k)=1+p+p^2+p^3+…+p^k\)
\(= (1+p+…+p^{\frac k 2})+(p^{\frac k 2+1}+…+p^k)\) \(= (1+p+…+p^{\frac k 2})+p^{\frac k 2+1}*(1+p+…+p^{\frac k 2})\) \(= (p^{\frac k 2+1}+1)*(1+p+…+p^{\frac k 2})\)
当k为偶数时
\(f(k)=f(k-1)*p^k\)
然后配合快速幂%9901
正解！！！
人已憔悴
Code：
#include#include #define ll long long#define Mod 9901using namespace std;ll a[30];ll s[30];bool b[10010];ll n,m;int t;ll ans=1;int read(){ int s=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { s=(s<<1)+(s<<3)+c-'0'; c=getchar(); } return s;}ll quickPow(ll a,ll b){ ll res=1; while(b>0) { if(b&1) res=(res*a)%Mod; b>>=1; a=(a*a)%Mod; } return res;}ll work(ll p,ll k){ if(k==1) return (p+1)%Mod; if(k==0) return 1; if(k&1) return work(p,k/2)*(quickPow(p,k/2+1)+1)%Mod; return ((work(p,k/2-1)*(quickPow(p,k/2)+1))%Mod+quickPow(p,k))%Mod;}int main(){ int i,j; n=read();m=read(); if(n%2==0) { a[++t]=2; while(n%2==0) { s[t]++; n/=2; } } for(i=3;i*i<=n;i+=2) if(!b[i]) { if(n%i==0) { a[++t]=i; while(n%i==0) { s[t]++; n/=i; } } j=i+i; while(j*j<=n) { b[j]=1; j+=i; } } if(n>1) { a[++t]=n; s[t]=1; } for(i=1;i<=t;i++) ans=(ans*work(a[i],s[i]*m))%Mod; printf("%lld",ans); return 0;}