本文主要是介绍poj-1845 Sumdiv nyoj - 928 小M的因子和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:求解A^B的因子和 mod 9901
先求解素因子,然后二分求解等比数列
#include<cstdio>
#include<cmath>
typedef long long LL;
const LL mod = 9901 ;
LL pow(LL a,LL b)
{LL res=1;while(b){if(b&1) res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;
}
LL fun(LL a,LL b)
{LL s,t;if(b==0) return 0;if(b==1) return a%mod;s=fun(a,b/2)%mod;if(b&1){t=pow(a,b/2+1)%mod;return (s*(t+1)+t)%mod;}else{t=pow(a,b/2)%mod;return (s*(t+1))%mod;}
}
int main()
{LL a,b,c,i,k;while(~scanf("%lld%lld",&a,&b)){if(a == 0) {printf("0\n");continue;}LL sum=1;for(i=2;i<=sqrt(a);i++){k=0;if(a%i==0){while(a%i==0){a/=i;k++;}sum=sum*(fun(i,k*b)+1)%mod;}}if(a>1) sum=sum*(fun(a,b)+1)%mod;printf("%lld\n",sum);}
}
这篇关于poj-1845 Sumdiv nyoj - 928 小M的因子和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!