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).
15 modulo 9901 is 15 (that should be output).
这道题目令我很不解的就是在等比求和的时候。大佬们分奇偶项数用二分递归求。而我的思路是乘法逆元*P1(P1^n -1)，也就是等比数列求和，在我出的数据中所得结果相同（rand随机出数)。。。不知道是什么原理
一开始想到的是A%mod^B，一举大数据直接炸。很快就想到唯一分解定理，然后等比求和，再然后就晾在等比求和上了。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include "cstdio"
using namespace std;
#define ll long long
#define mod 9901
#define N 1000010
ll prime[N];
bool vis[N];
ll p[N];
ll pn=0;
ll POW(ll a,ll n)
{
ll base=a,ret=1;
while(n)
{
if(n&1) ret=(ret%mod*base)%mod;
base=(base*base)%mod;
n>>=1;
}
return ret%mod;
}
__int64 sum(__int64 p,__int64 n) //递归二分求 (1 + p + p^2 + p^3 +...+ p^n)%mod
{ //奇数二分式 (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))
if(n==0) //偶数二分式 (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2)
return 1;
if(n%2) //n为奇数,
return (sum(p,n/2)*(1+POW(p,n/2+1)))%mod;
else //n为偶数
return (sum(p,n/2-1)*(1+POW(p,n/2+1))+POW(p,n/2))%mod;
}
int main()
{
for (int i = 2; i < N; i++) {
if (vis[i]) continue;
prime[pn++] = i;
for (int j = i; j < N; j += i)
vis[j] = 1;
}
ll a,b;
while(~scanf("%lld%lld",&a,&b))
{
memset(p,0,sizeof(p));
ll ans=1;
for(int i=0;prime[i]*prime[i]<=a;i++)
{
ll tem=0;
while(a%prime[i]==0)
{
tem++;
a/=prime[i];
}
if(tem)
{
p[prime[i]]=tem;
}
}
if(a!=1)
{
ll rev=POW(a-1,9899);
ll res=sum(a,b);
ans=ans*res%mod;
}
for(int i=0;i<pn;i++)
{ if(p[prime[i]])
{
ll rev=POW(prime[i]-1,9899);
ll res=sum(prime[i],p[prime[i]]*b);
ans=ans*res%mod;
}
}
cout<<ans<<endl;
}
}