POJ 1845 Sumdiv

escription

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

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).

A=p1^c1*p2^c2*p2^c3

所有因数和=(1+p1^1+....p1^c1)*(1+p2^1+....p2^c2)*(1+p3^1+...p3^c3)

等比数列求和

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long lol;
 8 lol Mod=9901,A,B,lim,ans;
 9 lol pri[10001],cnt[10001],tot;
10 lol qpow(lol x,lol y)
11 {
12   lol res=1;
13   while (y)
14     {
15       if (y&1) res=(res*x)%Mod;
16       x=(x*x)%Mod;
17       y/=2;
18     }
19   return res;
20 }
21 lol get_sum(lol x,lol y)
22 {
23   if (y==0) return 1;
24   if (y%2)
25       return ((qpow(x,y/2+1)+1)*get_sum(x,y/2))%Mod;
26   else
27       return ((qpow(x,y/2+1)+1)*get_sum(x,y/2-1)+qpow(x,y/2))%Mod;
28 }
29 int main()
30 {lol i,s;
31   cin>>A>>B;
32   lim=sqrt(A);
33   for (i=2;i<=lim;i++)
34     if (A%i==0)
35       {
36     s=0;
37     while (A%i==0)
38       {
39         s++;
40         A/=i;
41       }
42     pri[++tot]=i;
43     cnt[tot]=s*B;
44       }
45   if (A!=1)
46     {
47       pri[++tot]=A;
48       cnt[tot]=B;
49     }
50   ans=1;
51   for (i=1;i<=tot;i++)
52     {
53       ans=(ans*get_sum(pri[i],cnt[i]))%Mod;
54     }
55   cout<<ans;
56 }