首页 > 代码库 > Sumdiv
Sumdiv
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 20971 | Accepted: 5290 |
Description
Input
Output
Sample Input
2 3Sample Output
15Hint
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).
1 void Zhi() 2 { 3 int t = a; 4 for (int i=2;i*i<=a;i++) 5 { 6 if (t%i==0) 7 { 8 p[z]=i; 9 p_n[z]=1;10 t/=i;11 while (t%i==0)12 {13 p_n[z]++;14 t/=i;15 }16 z++;17 }18 if (t==1) break;19 if (i!=2)20 i++;//2.3.5.7.9...21 }22 if (t!=1)//本身就是质数23 {24 p[z]=t;25 p_n[z]=1;26 z++;27 }28 }
对于已经分解的整数A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)
有 A 的所有因子之和为
S = (1+p1+p1^2+p1^3+...p1^k1) * (1+p2+p2^2+p2^3+…+p2^k2) * (1+p3+ p3^3+…+p3^k3) * .... * (1+pn+pn^2+pn^3+...pn^kn)
但是，使用这个公式不能用等比求和公式，因为我们要求余，等比数列求和公式求余就错了
所以用到了二分求等比数列和
用递归二分求等比数列1+pi+pi^2+pi^3+...+pi^n：
（1）若n为奇数,一共有偶数项，则：
1 + p + p^2 + p^3 +...+ p^n
= (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2) * (1+p^(n/2+1))
= (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))
上式中加粗的前半部分恰好就是原式的一半，那么只需要不断递归二分求和就可以了，后半部分为幂次式，在后面就说快速幂。
（2）若n为偶数,一共有奇数项,则:
1 + p + p^2 + p^3 +...+ p^n
= (1+p^(n/2+1)) + p * (1+p^(n/2+1)) +...+ p^(n/2-1) * (1+p^(n/2+1)) + p^(n/2)
= (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2);
上式加粗的前半部分恰好就是原式的一半，依然递归求解
前提是要用到<同余模公式>
(a+b)%m=(a%m+b%m)%m
(a*b)%m=(a%m*b%m)%m
还有<快速幂>
应该不难，看看代码能懂
1 int Mi(int a, int b)//快速幂 2 { 3 int res = 1; 4 a %= MOD; 5 while (b) 6 { 7 if (b%2==1) 8 res = (res * a)%MOD; 9 a = (a * a)%MOD;10 b /= 2;11 }12 return res;13 }
好了，递归二分代码
1 int Erfen(int p , int n)//求 1 + p + p^2 + p^3+ ... +p^n2 {3 if (n==0) return 1;4 if (n%2==1)5 return ((Mi(p,n/2+1)+1) * Erfen(p,n/2))%MOD;6 else7 return ((1+Mi(p,n/2+1)) * Erfen(p,n/2-1) + Mi(p,n/2))%MOD;8 }
上总代码:
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 5 using namespace std; 6 7 #define MOD 9901 8 9 int a,b,z;10 int p[10000]; //质数11 int p_n[10000];//质数个数12 13 void Zhi()14 {15 int t = a;16 for (int i=2;i*i<=a;i++)17 {18 if (t%i==0)19 {20 p[z]=i;21 p_n[z]=1;22 t/=i;23 while (t%i==0)24 {25 p_n[z]++;26 t/=i;27 }28 z++;29 }30 if (t==1) break;31 if (i!=2)32 i++;//2.3.5.7.9...33 }34 if (t!=1)//本身就是质数35 {36 p[z]=t;37 p_n[z]=1;38 z++;39 }40 }41 42 int Mi(int a, int b)//快速幂43 {44 int res = 1;45 a %= MOD;46 while (b)47 {48 if (b%2==1)49 res = (res * a)%MOD;50 a = (a * a)%MOD;51 b /= 2;52 }53 return res;54 }55 56 int Erfen(int p , int n)//求 1 + p + p^2 + p^3+ ... +p^n57 {58 if (n==0) return 1;59 if (n%2==1)60 return ((Mi(p,n/2+1)+1) * Erfen(p,n/2))%MOD;61 else62 return ((1+Mi(p,n/2+1)) * Erfen(p,n/2-1) + Mi(p,n/2))%MOD;63 }64 65 int main()66 {67 while (scanf("%d%d",&a,&b)!=EOF)68 {69 z=0;//质数个数70 Zhi();71 72 int ans = 1;73 for (int i=0;i<z;i++)74 {75 ans = (ans * Erfen(p[i],p_n[i]*b))%MOD;76 }77 printf("%d\n",ans);78 }79 return 0;80 }
Sumdiv