Sumdiv
题目连接:
http://poj.org/problem?id=1845
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
题意
给你A,B,求A^B的因子和mod 9901
题解:
首先我们知道A的因式分解
A = (p1^k1) * (p2^k2) * (p3^k3) * .... * (pn^kn)
所以A^B = (p1^(k1*B)) * (p2^(k2*B)) * (p3^(k3*B)) * .... * (pn^(kn*B))
然后根据约数和定理,约数的和
Sum = (1+p1+p12+...+p1(k1*B))(1+p2....+p2(k2*B)).....(1+pn+...+pn(kn*B))
中间等比数列要mod,所以就直接递归求就好了。
代码
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<iostream>
using namespace std;
const int maxn = 1e6;
long long quickpow(long long m,long long n,long long k)
{
long long b = 1;
while (n > 0)
{
if (n & 1)
b = (b*m)%k;
n = n >> 1 ;
m = (m*m)%k;
}
return b;
}
int cnt[maxn];
int num[maxn];
int tot = 0;
void factorization(int x)
{
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
cnt[tot]=i;
num[tot]=0;
while(x%i==0)
{
x/=i;
num[tot]++;
}
tot++;
}
}
if(x!=1)
{
cnt[tot]=x;
num[tot]=1;
tot++;
}
}
long long Sum_of_geometric_progression(long long p,long long n,long long mod)
{
if(n==0)return 1;
if(n&1)
return ((1+quickpow(p,n/2+1,mod))%mod*Sum_of_geometric_progression(p,n/2,mod)%mod)%mod;
else
return (quickpow(p,n/2,mod)+(1+quickpow(p,n/2+1,mod))%mod*Sum_of_geometric_progression(p,(n-1)/2,mod)%mod)%mod;
}
int main()
{
int A,B;
while(scanf("%d%d",&A,&B)!=EOF)
{
tot = 0;
factorization(A);
int ans = 1;
for(int i=0;i<tot;i++)
ans = (ans*Sum_of_geometric_progression(cnt[i],B*num[i],9901))%9901;
printf("%d\n",ans);
}
return 0;
}