大家好，又见面了，我是全栈君。
Sumdiv
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 13959 | Accepted: 3433 |
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).
Source
思路看：
http://hi.baidu.com/necsinmyway/item/9f10b6d96c5068fbb2f77740
AC代码：
#include<iostream>using namespace std;#define LL long longLL pow_mod(LL a,LL n,int mod){ //高速幂 LL r=1; LL base=a; while(n){ if(n&1) r=r*base%mod; base=base*base%mod; n>>=1; } return r%9901;}LL sum(LL a,LL b,LL mod){ //二分求等比数列前N项和 if(b==0) return 1; if(b%2==1) return (sum(a,b/2,mod)*(pow_mod(a,b/2+1,mod)+1))%mod; else return (sum(a,b-1,mod)+pow_mod(a,b,mod))%mod;}int main(){ LL a,b; LL ans; while(cin>>a>>b){ ans=1; for(LL i=2;i*i<=a;i++){ //将a分解为质数的乘积 if(a%i==0){ LL s=0; while(a%i==0){ s++; a/=i; } ans=ans*sum(i%9901,b*s,9901)%9901; } } if(a>=2){ ans=ans*sum(a%9901,b,9901)%9901; } cout<<ans<<endl; } return 0;}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115395.html原文链接：https://javaforall.net
