给定A,B，求AB的所有约数之和，答案mod 9901
数据范围：
0 ≤ A,B ≤ 5*107
# 题解
A分解质因数后为p1c1*p2c2*......pncn
AB=p1c1*B*p2c2*B*......pncn*B
那么AB的约数之和就是
(p10+p11+....p1c1*B)*(p20+p21+....p2c2*B)*......*(pn0+pn1+....pncn*B)
分解质因数后对每一项等比数列求和
每一项的求和公式为：(1-pici*B+1)/(1-pi)
（pici*B+1-1) / (pi-1)
分母快速幂求得mod9901的值
因为9901为质数，只要pi-1不是他的倍数，就互质，根据费马小定理可以求出逆元，
如果是倍数，那么pi mod 9901为1
所以等比数列和就是B*ci+1
1 #include<bits/stdc++.h> 2 #define pll pair<long long,long long> 3 #define ll long long 4 using namespace std; 5 const int mod=9901; 6 pll factor[2000]; 7 int cntf; 8 ll qmi(ll a,ll k){ 9 ll res=1; 10 while(k){ 11 if(k&1) res=res*a%mod; 12 a=a*a%mod; 13 k>>=1; 14 } 15 return res % mod; 16 } 17 void get(ll a){ 18 for(ll i=2;i<=a/i;i++){ 19 if(a%i==0){ 20 int num=0; 21 while(a%i==0){ 22 num++; 23 a/=i; 24 } 25 factor[cntf++]={i,num}; 26 } 27 } 28 if(a>1) factor[cntf++]={a,1}; 29 } 30 int main(){ 31 ll a,b; 32 cin>>a>>b; 33 if(a==0)//特判 34 { 35 puts("0"); 36 return 0; 37 } 38 get(a); 39 ll ans=1; 40 for(int i=0;i<cntf;i++){ 41 int p=factor[i].first; 42 int n=factor[i].second; 43 if((p-1)%mod ==0){ 44 ans=(ans%mod * (b%mod*n%mod+1)%mod)%mod; 45 } 46 else{ 47 ll x=((qmi(p,b*n+1)-1)%mod+mod)%mod;// qmi求得的结果-1后可能为负数 48 ll y=qmi(p-1,mod-2); 49 ans=((ans*x)%mod*y)%mod; 50 } 51 } 52 cout<<ans<<endl; 53 return 0; 54 }
原文：https://www.cnblogs.com/hhyx/p/12642908.html