题目链接:http://poj.org/problem?id=1958
求A的B次方的所有约数之和对9901的模。使用分治算法计算等比数列的前缀和,时间复杂度为O(logC)
代码如下:
#include<iostream> #include<vector> using namespace std; #define ll long long #define maxn 1000 const ll p=9901; int n; ll ksm(ll a,ll b){//快速幂 ll ans=1; a%=p; while(b){ if(b&1)ans=(ans*a)%p; b>>=1; a=(a*a)%p; } return ans; } vector<pair<ll,ll>> w; void fj(ll a){//分解质因数并且存在w中 ,a=p1^k1*p2^k2...ps^ks for(ll i=2;i*i<=a;i++){ if(!(a%i)){ ll num=0; while(!(a%i)){ num++; a/=i; } w.push_back(make_pair(i,num)); } } if(a!=1)w.push_back(make_pair(a,1));//大于根号a的质因数,最多只会有一个 } ll sum(ll a,ll c){//分治,计算1+a^1+a^2+...+a^c if(!a)return 0; if(!c)return 1; if(c&1)return ( (1+ksm(a,(c+1)/2))*sum(a,c/2) )%p; return ( (1+ksm(a,c/2))*sum(a,c/2-1)+ksm(a,c) )%p; } ll a,b; int main(){ cin>>a>>b; fj(a);//对a分解质因数 ll ans=1; for(int i=0;i<w.size();i++){ ll s=w[i].first; ll t=w[i].second; (ans*=sum(s,b*t))%=p; } cout<<ans<<endl; }