快速幂+等比数列求和。。。。
Sumdiv
| Time Limit: 1000MS |
|
Memory Limit: 30000K |
| Total Submissions: 12599 |
|
Accepted: 3057 |
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).
Source
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MOD=9901;
typedef long long int LL;
int p[10000],n[10000],k,A,B;
LL power(LL p,LL n) ///p^n
{
LL ans=1;
while(n>0)
{
if(n&1)
ans=(ans*p)%MOD;
n>>=1;
p=(p*p)%MOD;
}
return ans%MOD;
}
LL Spower(LL p,LL n) ///1+p^1+p^2+p^3+....+p^n-1+p^n
{
if(n==0) return 1;
if(n&1)
return ((Spower(p,n/2)%MOD)*((1+power(p,n/2+1))%MOD))%MOD;
else
return (((Spower(p,n/2-1)%MOD)*(1+power(p,n/2+1))%MOD)%MOD+power(p,n/2)%MOD)%MOD;
}
int main()
{
while(scanf("%d%d",&A,&B)!=EOF)
{
k=0;
for(int i=2;i*i<=A;)
{
if(A%i==0) p[k]=i,n[k]=0,k++;
while(A%i==0)
{
n[k-1]++;
A/=i;
}
if(i==2) i++;
else i+=2;
}
if(A!=1)
{
p[k]=A;
n[k++]=1;
}
LL ans=1;
for(int i=0;i<k;i++)
{
ans=(ans*Spower(p,B*n))%MOD;
}
printf("%I64d\n",ans);
}
return 0;
}
|
* This source code was highlighted by YcdoiT. ( style: Codeblocks )