# POJ 1845 Sumdiv （数论，约数和）

Sumdiv

 Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 20130 Accepted: 5082

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

### 思路

a^b=P1^(m1∗b)∗P2^(m2∗b)∗...∗Pn^(mn∗b)

### AC代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define mod 9901

typedef unsigned long long LL;

LL mult(LL a,LL n)
{
LL ans=1;
while(n)
{
if(n&1)ans=(a*ans)%mod;
a=(a*a)%mod;
n>>=1;
}
return ans;
}

/* 乘法逆元求解等比数列前n项和：status WA
LL solve(int a,int b)
{
return ((mult(a,b+1)-1)*mult(a-1,9901-2))%mod;
}*/

LL sum(LL p,LL n)  //等比求和
{
if(n==0)return 1;
if(n&1)return ( (1+mult(p,n/2+1)) * sum(p,n/2) ) % mod;
return ((1+mult(p,n/2+1)) * sum(p,n/2-1) + mult(p,n/2) )% mod;
}

void numberfixed(LL n,LL m)
{
LL s=1;
for(LL i=2; i*i<=n; i++)
if(n%i==0)
{
int b=0;
while(n%i==0)
{
b++;
n/=i;
}
s=(s*sum(i,b*m))%mod;
}
if(n!=1)
s=(s*sum(n,m))%mod;
printf("%I64d\n",s);
}

int main()
{
LL a,b;
while(~scanf("%I64d%I64d",&a,&b))
{
if(a==0)printf("0\n");
else numberfixed(a,b);
}
return 0;
}