求A^B的所有约数和 POJ1845

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 
 8 long long arr1[100000];
 9 long long MOD=9901;
10 
11 long long multi(long long a,long long b)
12 {
13     if(b==0)
14         return 1;
15     if(b==1)
16         return a;
17     long long ret=multi(a,b/2);
18     ret=(ret*ret)%MOD;
19     if(b&1)
20         ret=ret*a%MOD;
21     return ret;
22 }
23 
24 long long fsum(long long p,long long n)  //递归二分求 (1 + p + p^2 + p^3 +...+ p^n)%mod
25 {                          //奇数二分式 (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))
26     if(n==0)               //偶数二分式 (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2)
27         return 1;
28     if(n%2)  //n为奇数,
29         return (fsum(p,n/2)*(1+multi(p,n/2+1)))%MOD;
30     else     //n为偶数
31         return (fsum(p,n/2-1)*(1+multi(p,n/2+1))+multi(p,n/2))%MOD;
32 }
33 
34 int main()
35 {
36     long long a,b;
37     while(scanf("%I64d%I64d",&a,&b)!=EOF)
38     {
39         memset(arr1,0,sizeof(arr1));
40         long long sum=a;
41         long long ans1=1;
42         double s=sqrt((double)a);
43         int num=0;
44         for(int i=2;i<=s;i++)
45         {
46             int flag=0;
47             while(sum%i==0)
48             {
49                 sum=sum/i;
50                 flag++;
51                 arr1[num]=i;
52             }
53             if(flag)
54             {
55                 flag*=b;
56                 num++;
57                 ans1=(ans1*fsum(arr1[num-1],flag))%MOD;
58            //     cout<<arr1[num-1]<<" "<<flag<<endl;
59            //     cout<<ans1<<endl;
60             }
61         }
62         if(sum!=1)
63         {
64             arr1[num]=sum;
65             ans1=(ans1*fsum(sum,b))%MOD;
66             num++;
67         }
68         cout<<ans1<<endl;
69     }
70     return 0;
71 }

View Code

求一个数的所有约数和

ans=（1+q1^1+q1^2+......+q1^k1)*(1+q2^1+q2^2+......+q2^k2)*......(1+qn^1+qn^2+......qn^kn)

此题不能用等比数列前n项和，因为要求逆元需要该数与MOD互质，而此题中MOD过小，该数可能为MOD的整数倍，所以要用二分的方法直接求

（1+p+p^2+p^3)=(1+p)*(1+p^2)