首页 > 代码库 > POJ 1845 Sumdiv
POJ 1845 Sumdiv
Sumdiv
Description
Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).
Input
The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.
Output
The only line of the output will contain S modulo 9901.
Sample Input
2 3
Sample Output
15
Hint
2^3 = 8.
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).
运用不少知识点来自这点击打开链接
AC代码如下:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define mod 9901 #define M 10000 #define ll long long using namespace std; ll power(ll d,ll p)//幂次的优化 { ll ans=1; while(p>0) { if(p%2) ans=(ans*d)%mod; p/=2; d=(d*d)%mod; } return ans; } ll sum(ll d,ll p)//等比数列求和递归 { if(p==0) return 1; if(p==1) return 1+d; if(p%2==1) return sum(d,p/2)*(1+power(d,p/2+1))%mod; else return (sum(d,p/2-1)*(1+power(d,p/2))%mod+power(d,p))%mod; } int main() { int i,j; int a,b; while(~scanf("%d%d",&a,&b)) { int ds[M]; int po[M]; int tt=0; for(i=2;i*i<=a;)//求a的因子 { if(a%i==0) { ds[tt]=i; po[tt]=0; while(!(a%i)) { po[tt]++; a/=i; } tt++; } i==2?i++:i+=2; } if(a!=1) { ds[tt]=a; po[tt++]=1; } ll ans = 1; for(i=0;i<tt;i++) ans=(ans*(ll)sum(ds[i],po[i]*b))%mod; printf("%I64d\n",ans); } }
POJ 1845 Sumdiv
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。