Sumdiv Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 21310   Accepted: 5360 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).  逆元知识http://blog.csdn.net/acdreamers/article/details/8220787 //本题的思路非常巧妙 //题目大意是求A^B的所有约数（即因子）之和，并对其取模9901再输出 //此处用的等比数列求和公式和用到逆元的知识：a/b mod c = (a mod (b*c))/ b //二分亦可解之 //int 2147483648～2147483647 大约是2*10^9 #include #include using namespace std; #define ll long long const int mod=9901; ll Mod; ll A,B; ll fast_multi(ll x,ll y){ ll ans=0; while(y){ if(y&1) ans=(ans+x)%Mod; y>>=1; x=(x+x)%Mod; } return ans; } ll fastpow(ll P,ll n){//快速幂 ll ans=1; while(n){ if(n&1) ans=fast_multi(ans,P);//两数直接相乘溢出 n>>=1; P=fast_multi(P,P);//两数直接相乘溢出 } return ans; } int main(){ while(~scanf("%lld%lld",&A,&B)){ int n; int ans=1; for(int i=2;i*i<=A;i++){//如果改成i<=A,则i最后是一个很大的素数 if(A%i==0){ n=0; while(A%i==0){ n++; A/=i; } Mod=mod*(i-1); ans=(ans*(fastpow(i,B*n+1)-1)/(i-1))%mod;//B*n+1超出了int的范围 } } if(A>1){ Mod=mod*(A-1); ans=(ans*(fastpow(A,B+1)-1)/(A-1))%mod; } printf("%d ",ans); } return 0; }