poj1845 数论快速幂

Sumdiv

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 16466		Accepted: 4101

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

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^B的所有因子的和之后再mod 9901的值。

(1+a1+a1^2+...a1^n1)*(1+a2+a2^2+...a2^n2)*(1+a3+a3^2+...a3^n2)*...(1+am+am^2+...am^nm) mod 9901。

对于每一个(1+a1+a1^2+...a1^n1) mod 9901

等于 (a1^(n1+1)-1)/(a1-1) mod 9901，这里用到逆元的知识：a/b mod c = (a mod (b*c))/ b

所以就等于(a1^(n1+1)-1)mod (9901*(a1-1)) / (a1-1)。

至于前面的a1^(n1+1)，快速幂。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #define mod 9901
 7 #define N 10007
 8 #define ll long long
 9 using namespace std;
10 
11 int prime[10007];
12 
13 void getPrime()
14 {
15     for(int i=2;i<=10000;i++)
16     {
17         if(!prime[i])prime[++prime[0]]=i;
18         for(int j=1;j<=prime[0]&&prime[j]*i<=10000;j++)
19         {
20             prime[prime[j]*i]=1;
21             if(i%prime[j]==0) break;
22         }
23     }
24 }
25 
26 long long factor[100][2];
27 int fatCnt;
28 int getFactors(long long x)
29 {
30     fatCnt=0;
31     long long tmp=x;
32     for(int i=1;prime[i]<=tmp/prime[i];i++)
33     {
34         factor[fatCnt][1]=0;
35         if(tmp%prime[i]==0)
36         {
37             factor[fatCnt][0]=prime[i];
38             while(tmp%prime[i]==0)
39             {
40                 factor[fatCnt][1]++;
41                 tmp/=prime[i];
42             }
43             fatCnt++;
44         }
45     }
46     if(tmp!=1)
47     {
48         factor[fatCnt][0]=tmp;
49         factor[fatCnt++][1]=1;
50     }
51     return fatCnt;
52 }
53 long long pow_m(long long a,long long n)//快速模幂运算
54 {
55     ll ans=1;a%=mod;
56     while(n)
57     {
58         if (n&1) ans=(ans*a)%mod;
59         n>>=1;
60         a=(a*a)%mod;
61     }
62     return ans;
63 }
64 long long sum(long long p,long long n)//计算1+p+p^2+````+p^n
65 {
66     if(p==0)return 0;
67     if(n==0)return 1;
68     if(n&1) return ((1+pow_m(p,n/2+1))%mod*sum(p,n/2)%mod)%mod;
69     else return ((1+pow_m(p,n/2+1))%mod*sum(p,n/2-1)+pow_m(p,n/2)%mod)%mod;
70 
71 }
72 int main()
73 {
74     int A,B;
75     getPrime();
76     while(~scanf("%d%d",&A,&B))
77     {
78         getFactors(A);
79         long long ans=1;
80         for(int i=0;i<fatCnt;i++)
81             ans=(ans*sum(factor[i][0],B*factor[i][1])%mod)%mod;
82         printf("%lld
",ans);
83     }
84 }

poj1845 数论 快速幂

poj1845 数论快速幂