Sumdiv
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 22680 | Accepted: 5660 |
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).
The natural divisors of 8 are: 1,2,4,8. Their sum is 15.
15 modulo 9901 is 15 (that should be output).
Source
【题目大意】
求A^B的所有约数的和
【题解】
把A唯一分解，不难得到答案：
(1+p1+p1^2+……+p1^(φ1*B)) × (1+p2+p2^2+
……+p2^(φ2*B)) ×……× (1+pn+pn^2+……+pn^(φn*B))
问题转化为等比数列求和，此处MOD为质数，存在逆元，但对于更一般的情况，采用分治法，复杂度多一个Log
cal(p,k) = p^0 + p^1 + p^2 + ... + p^k
if k&1
cal(p,k) = (1 + p^((k + 1)/2))*cal(p, (k-1)/2)
else
cal(p,k) = (1 + p^(k/2)) * cal(p, k/2 - 1) + p^k
快速幂即可
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cstdlib> 6 #include <cmath> 7 8 const int INF = 0x3f3f3f3f; 9 const int MAXN = 50000000 + 10; 10 const int MOD = 9901; 11 12 inline void read(int &x) 13 { 14 x = 0;char ch = getchar();char c = ch; 15 while(ch > '9' || ch < '0')c = ch, ch = getchar(); 16 while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar(); 17 if(c == '-')x = -x; 18 } 19 20 int a,b,cnt,xishu[5010],zhishu[5010],ans; 21 22 int pow(int p, int k) 23 { 24 int r = 1, base = p; 25 for(;k;k >>= 1) 26 { 27 if(k & 1)r = ((long long)r * base) % MOD; 28 base = ((long long)base * base % MOD); 29 } 30 return r % MOD; 31 } 32 33 //求解1 + p + p^2 + p^3 + ... + p^k 34 int cal(int p, int k) 35 { 36 if(k == 0) return 1; 37 if(k == 1) return (p + 1) % MOD; 38 if(k & 1) return ((long long)(1 + pow(p, (k + 1)/2)) * (long long)(cal(p, (k - 1)/2))%MOD) % MOD; 39 else return((long long)(pow(p, k/2) + 1) * (long long)(cal(p, k/2 - 1)) % MOD + pow(p, k)) % MOD; 40 } 41 42 int main() 43 { 44 read(a),read(b); 45 register int nn = sqrt(a) + 1; 46 for(register int i = 2;i <= nn && a > 1;++ i) 47 if(a % i == 0) 48 { 49 zhishu[++cnt] = i; 50 while(a % i == 0) ++ xishu[cnt], a /= i; 51 } 52 if(a > 1)zhishu[++cnt] = a, xishu[cnt] = 1; 53 ans = 1; 54 for(register int i = 1;i <= cnt;++ i) 55 { 56 ans *= cal(zhishu[i], xishu[i] * b); 57 ans %= MOD; 58 } 59 printf("%d", ans%MOD); 60 return 0; 61 }