Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 20029 | Accepted: 5058 |
Description
Input
Output
Sample Input
2 3
Sample Output
15
Hint
Source
代码:
#include<cstdio> #include<cstring> #ifdef unix #define LL "%lld" #else #define LL "%I64d" #endif #define mod 9901 using namespace std; typedef long long ll; const int N=1e5+10; ll tot,c[N/3],prime[N/3]; bool check[N]={1,1}; void get_prime(){ ll n=10010; for(ll i=2;i<=n;i++){ if(!check[i]) prime[++tot]=i; for(ll j=1;j<=tot&&i*prime[j]<=n;j++){ check[i*prime[j]]=1; if(i%prime[j]==0) break; } } } ll mul(ll a,ll p,ll M){ ll res=0; for(;p;p>>=1,a=(a+a)%M) if(p&1) res=(res+a)%M; return res; } ll fpow(ll a,ll p,ll M){ ll res=1; for(;p;p>>=1,a=mul(a,a,M)) if(p&1) res=mul(res,a,M); return res; } void factor(ll A,ll B){ ll ans=1; for(ll i=1;prime[i]*prime[i]<=A;i++){ if(A%prime[i]==0){ ll num=0; while(A%prime[i]==0) num++,A/=prime[i]; ll MOD=(prime[i]-1)*mod; ans*=(fpow(prime[i],num*B+1,MOD)+MOD-1)/(prime[i]-1); ans%=mod; } } if(A>1){ ll MOD=mod*(A-1); ans*=(fpow(A,B+1,MOD)+MOD-1)/(A-1); ans%=mod; } printf(LL"\n",ans); } int main(){ get_prime(); for(ll A,B;scanf(LL LL,&A,&B)==2;) factor(A,B); return 0; }
原文:http://www.cnblogs.com/shenben/p/6264322.html