题目链接：http://poj.org/problem?id=1845
先分解质因数，然后求等比数列和，如果p-1和mod=9901不是互质的话由于9901是质数，所以p-1一定是mod的倍数，这个时候直接算出和即可，对于互质的，直接使用费马小定理
在O(logn)时间内求出逆元，与分子相乘即可，其中要注意的是分子-1之后再对mod取模可能会使得模数为负，所以需要加上一个mod在取模，保证模数是正数。
代码：
#include<iostream> #include<vector> #include<cstring> using namespace std; const int mod=9901; typedef long long ll; int a,b; vector< pair<int,int> > v; ll pow(ll a,ll b){ ll ans=1; while(b){ if(b&1)ans=(ans*a)%mod; a=(a*a)%mod; b>>=1; } return ans; } int main(){ cin>>a>>b; int tmp=a; for(int i=2;i*i<tmp;i++){ if(tmp%i)continue; int cnt=0; while(tmp%i == 0)tmp/=i,cnt++; v.push_back(make_pair(i,cnt)); } if(tmp>1)v.push_back(make_pair(tmp,1)); ll ans=1; for(int i=0;i<v.size();i++){ int p=v[i].first,c=v[i].second; if(p%mod==1){ ans=(ans*(b*c%mod+1))%mod; }else{ int x=((pow(p,b*c+1)-1)%mod+mod)%mod;//最小正整数 int y=pow(p-1,mod-2); ans = (ans*x%mod)*y%mod; } } cout<<ans<<endl; }