poj 1845 数论

2019-04-14 18:41发布

站内文章 / 模拟电子
11262 0 1516
题意： 求A^B所有因子的和模9901的值 分析： 对于A我们可以分解为  所以A^B可以分解为 那么所求的值为：  等比数列求和以为涉及除法和模所以需要逆元 参考http://blog.csdn.net/acdreamers/article/details/8220787blog ACcode： #include #include #include #include #include #include using namespace std; #define eps 1e-6 #define mod 9901 #define ll long long int p[mod+100]; bool prime[mod+100]; int cnt; void get_prime(){ cnt=0; memset(prime,true,sizeof(prime)); for(int i=2;i>=1; a=(a+a)%m; } return ans; } ll pow(ll a,ll b,ll m){ ll ans=1; while(b){ if(b&1)ans=q_mul(ans,a,m); b>>=1; a=q_mul(a,a,m); } return ans; } int main(){ ll a,b; get_prime(); while(cin>>a>>b){ ll ans=1; for(int i=0;p[i]*p[i]<=a;++i){ if(a%p[i]==0){ int num=0; while(a%p[i]==0){ num++; a/=p[i]; } ll m=(p[i]-1)*mod; ans*=(pow(p[i],num*b+1,m)+m-1)/(p[i]-1); ans%=mod; } } if(a>1){ ll m=mod*(a-1); ans*=(pow(a,b+1,m)+m-1)/(a-1); ans%=mod; } cout<

热门文章