Sumdiv
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 17387 | Accepted: 4374 |
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用唯一分解定理分解 A = p1 ^ a1 * p2 ^ a2 * p3 ^ a3 ... * pn ^ an
其中A的因子的个数为 （ 1 + a1) * ( 1 + a2 ) * ( 1 + a3 ) * ... * ( 1 + an)
则A的所有因子的和为 （1 + p1 + p1 ^ 2 + p1 ^ 3 ... + p1 ^ a1) * ( 1 + p2 ^ 1 + p2 ^ 2 + p3 ^ 3 + ... + p2 ^ a2 ) * ... * ( 1 + pn + pn ^ 2 + ... + pn ^ an)
求 a + a ^ 2 + a ^ 3 + ... + a ^ n
如果n为奇数： a + a ^ 2 + ... + a ^ (n / 2 ) + a ^ (n / 2 + 1) + ( a + a ^ 2 + ... + a ^ ( n / 2 ) ) * a ^ ( n / 2 + 1）
如果n为偶数： a + a ^ 2 + ... + a ^ (n / 2 ） + （ a + a ^ 2 + ... + a ^ ( n /. 2) ) * a ^ (n / 2)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int Max = ;
const int Mod = ;
int prime[Max + ],flag[Max],cnt;
void get_prime()
{
cnt = ;
memset(flag, , sizeof(flag));
for(int i = ; i <= Max; i++)
{
if(flag[i] == )
{
flag[i] = ;
prime[++cnt] = i;
for(int j = i; j <= Max / i; j++)
flag[i * j] = ;
}
}
}
LL pow_mod(LL n, LL k)
{
LL res = ;
while(k)
{
if(k & )
res = res * n % Mod;
n = n * n % Mod;
k >>= ;
}
return res;
}
LL get_sum(LL n, LL m)
{
if(m == )
return ;
if(m & )
{
return get_sum(n, m / ) *( + pow_mod(n, m / + ) ) % Mod;
}
else
{
return ( get_sum(n, m / - ) * ( + pow_mod(n, m / + )) % Mod + pow_mod(n, m / ) ) % Mod;
}
}
int main()
{
LL a,b;
get_prime();
while(scanf("%I64d%I64d", &a, &b) != EOF)
{
LL ans = ;
if(a == && b) //特殊情况
ans = ;
LL m;
for(int i = ; i <= cnt; i++)
{
if(prime[i] > a)
break;
m = ;
if(a % prime[i] == )
{
while(a % prime[i] == )
{
a = a / prime[i];
m++;
}
m = m * b; // m要设成LL，否则这里会溢出
ans = ans * get_sum((LL)prime[i], m) % Mod;
}
}
if(a > )
ans = ans * get_sum(a, b) % Mod;
printf("%I64d\n", ans);
}
return ;
}