【题目】
输入两个正整数\(a\)和\(b\)，求\(a^{b}\)的因子和。结果太大，只要输出它对\(9901\)的余数。
输入格式：
仅一行，为两个正整数\(a\)和\(b\)(\(0≤a,b≤50000000\))。
输出格式：
\(a^b\)的因子和对\(9901\)的余数。
【Input】
2 3【Output】
15【分析】
先将\(a\)分解质因数，得：
\[p_1^{c_1}*p_2^{c_2}*p_3^{c_3}*……*p_n^{c_n}\]
则有\(a^b\)：
\[p_1^{c_1*b}*p_2^{c_2*b}*p_3^{c_3*b}*……*p_n^{c_n*b}\]
对于每个\(p_i^{k_i}(k_i=c_i*b,i\in[1,n])\)的约数有：\(p_i^1,p_i^2……p_i^k\)
所以：\[sum=\prod_{i=1}^{n}{\sum_{j=0}^{k}{p_i^j}}\]
于是我们可以写一个\(GetSum(p,c)\)来计算\(\sum_{j=0}^{k}{p_i^j}\)，为了减少复杂度，我们可以利用\(c\)的奇偶分\(2\)种情况处理。
第一种，为偶数：\[GetSum(p,c)=(1+p^{c/2})*GetSum(p,c/2-1)+p^c\]
第二种，为奇数：\[GetSum(p,c)=(1+p^{(c+1)/2})*GetSum(p,(c-1)/2)\]
最后，一定要开\(long long！！！\)
【代码】
#include<cstdio>
#define mod 9901
using namespace std;
typedef long long ll;
ll sum=1;
ll a,b,cnt;
ll p[50000],c[500];
void doit(){ //分解a
ll k=a;
for(ll i=2;i*i<=k;i++)
if(k%i==0){
p[++cnt]=i;
while(k%i==0){
c[cnt]++;
k/=i;
}
}
if(k>1) p[++cnt]=k,c[cnt]++;
for(ll i=1;i<=cnt;i++) c[i]*=b;
}
ll QuickPow(ll x,ll y){ //快速幂
ll ret=1;
while(y){
if(y&1) ret=ret*x%mod;
x=x*x%mod;
y>>=1;
}
return ret;
}
ll GetSum(ll x,ll y){
if(y==0) return 1;
if(y%2==0) return (((1+QuickPow(x,y/2))%mod)*(GetSum(x,y/2-1)%mod)+QuickPow(x,y))%mod;
else return ((1+QuickPow(x,(y+1)/2))%mod)*(GetSum(x,(y-1)/2)%mod)%mod;
}
int main(){
scanf("%lld%lld",&a,&b);
doit();
for(ll i=1;i<=cnt;i++) sum=sum*GetSum(p[i],c[i])%mod;
printf("%lld",sum);
return 0;
}