输入两个正整数\(a\)和\(b\)，求\(a\cdot b\)的因子和。结果太大，只要输出它对9901的余数。
Input
仅一行，为两个正整数\(a\)和\(b\)(\(0≤a,b≤50000000\))。
Output
a^b的因子和对9901的余数。
Sample Input
2 3
Sample Output
15
题意：
中文题面，不解释。
题解：
将\(a^b\)分为\(b\)个\(a\)相乘，然后再处理。
设
\(a=p_1^{c_1}p_2^{c_2}…p_n^{c_n}\)
则\(a\)的所有因数和为
\(\sum_{i_1=0}^{c_1}\sum_{i_2=0}^{c_2}…\sum_{i_n=0}^{c_n}p_1^{i_1}p_2^{i_2}…p_n^{i_n}\)
然后我们可以发现每个因数是独立的，可以提出来变成
\(\prod_{i=1}^{n}\sum_{j=0}^{c_i}p_i^j\)
现在可以对每一个因数分开处理了
拆开\(\sum\)发现变成了一个等比数列：
\(1+p^1+p^2+p^3+…+p^c\)
然后套一下等比数列的公式成了
\(\frac{p^{c-1}-1}{p-1}\)
最后答案就是
\(\prod_{i=1}^n\frac{p_i^{c_i-1}-1}{p_i-1}\)
额，还要乘上\(b\)
\(\prod_{i=1}^n\frac{p_i^{c_ib-1}-1}{p_i-1}\)
这里的分母就要用逆元来乘，但因为有时\(p_i-1\)会是9901的倍数，这时直接把答案乘上这个因数的个数就行了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll p=9901;
ll mpow(ll a,ll n){
ll ret=1;
while(n){
if(n&1)ret=ret*a%p;
a=a*a%p;
n/=2;
}
return ret;
}
ll a,b,ans=1;
ll prime[1000000],js[1000000],m;
main(){
cin>>a>>b;
int n=a;
for(ll i=2;i*i<=n;++i){
if(n%i==0)prime[++m]=i;
while(n%i==0){
js[m]++;
n/=i;
}
}
if(n!=1){
prime[++m]=n;
js[m]=1;
}
for(ll i=1;i<=m;++i){
if(prime[i]%p==1){
ans=(ans*(js[i]+1))%p;
continue;
}
ll S=(mpow(prime[i],js[i]*b+1)-1)*mpow(prime[i]-1,p-2)%p;
ans=(ans*S)%p;
}
cout<<ans%p<<endl;
}