题意就是输入 a,b 输出 a的b次方的因子求和并对9902 取模
这题可以对因子化简
由于唯一分解定理 可以把a表示成 p1^q1*p2^q2...*pn^qn
也就是说 a^b = p1^(q1*b)*p2^(q2*b)...*pn^(qn*b)
由于约数和公式可得a^b得约数求和为(1+p1+p1^2+p1^3+...p1^(q1*b))(1+p2+p2^2+p2^3+...p2^(q2*b))...(1+pn+pn^2+pn^3+...pn^(qn*b))
故问题转化成了如何求等比数列得问题
我们再看 1+p1+p1^2+p1^3+...p1^(q1*b) 可以对其因式分解 从而简化计算
若q*b是偶数 那么一共为奇数项 最终可以化简为 （1+p^(n/2+1) )*（1+p+p^2+...p^(n/2-1)）+p^(n/2)
若q*b是奇数 那么一共为偶数项 化简为--> （1+p+p^2+...p^(n/2)*(1+p^(n/2+1))
其中都可以利用一个二分的思想 就是把数列拆开来算
code：
#include<iostream> #include<cstdio> #include<cmath> #include<vector> using namespace std; typedef long long ll; const int maxn = 50000000; const int mod = 9901; vector<int>p; int size,a,b; bool vis[20005]; void prime() { for(int i=2;i*i<=maxn;i++) { if(!vis[i]) { p.push_back(i); for(int j=i+i;j*j<=maxn;j+=i)vis[j]=1; } } } ll fun(ll aa,ll bb) { ll ans = 1; aa%=mod; while(bb) { if(bb&1)ans = ans*aa %mod; bb>>=1; aa = aa*aa%mod; } return ans%=mod; } ll bi(ll x,ll n) { if(n==0)return 1; else { if(n%2)return (bi(x,n/2)*( 1 + fun(x,n/2+1 ) ))%mod; else return ( bi(x,n/2-1)*( 1 + fun(x,n/2+1 ) )+fun(x,n/2))%mod; } } ll solve() { ll ans=1; ll t = a; for(int i=0;p[i]*p[i]<=a;i++) { ll tem =0; //cout<<p[i]<<endl; //system("pause"); while(t%p[i]==0)tem++,t/=p[i]; tem*=b; ans*=bi(p[i],tem),ans%=mod; } if(t!=1)ans*= bi(t,b)%mod,ans%=mod; return ans%mod; } int main() { ios::sync_with_stdio(0); prime(); cin>>a>>b; if(b==0||a<=1)cout<<1<<endl; else cout<<solve()<<endl; return 0; } #include<iostream> #include<cstdio> using namespace std; const int maxn = 50000000; const int lim = 10005; const int mod = 9901; typedef long long ll; ll a,b,p[lim],sze; bool vis[50005]; void prime() { for(int i=2;i<50005;i++) { if(!vis[i]){ p[sze++] = i; for(int j=i+i;j<50005;j+=i)vis[j]=1; } } } ll fun(ll aa,ll bb,ll m) { ll ans = 1; aa%=m; while(bb){ if(bb&1)ans = ans*aa%m; bb>>=1; aa = aa*aa%m; } return ans%m; } ll solve() { ll ans=1; ll c =a; for(int i=0;p[i]*p[i]<=c;i++){ ll tem =0; while(c%p[i]==0)tem++,c/=p[i]; if(tem){ // cout<<p[i]<<" "<<tem<<" "<<c<<endl; ll m = (mod*(p[i]-1)); ans = ans*(((fun(p[i],(tem)*b+1,m)-1+m))/(p[i]-1)),ans%=mod; } } // cout<<c<<endl; if(c>1){ ll m = (mod*(c-1)); //cout<<c<<endl; ans = ans*(((fun(c,b+1,m)-1+m))/(c-1)),ans%=mod; } return ans; } int main() { prime(); cin>>a>>b; cout<<solve()<<endl; return 0; }