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.OutputThe 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).
题意：求AB的所有约数的和 % MOD （9901） 题意中有点问题，我们知道0是没有约数的，我觉得A、B应该都是>0的
思路：我们可以把A分解质因数（p1c1 * p2c2 * .... * pncn）B
约数和：（1 + p1 + p12 + ... + p1B*c1）* （1 + p2 + p22 + ... + p2B*c2）* .... * （1 + pn + pn2 + ... + pnB*cn） （ 排列组合问题）
这样我们可以看出这是多个等比数列乘积，可以用等比数列求和公式 （a1 *（1-qn））/（1-q）,我们注意到这里有除法，但是同余模定理是对于加减乘的，那么我们可以利用费马小定理，
求出（1-q）的逆元，然后把除变成乘逆元
坑点：应为 9901 这个质数较小，很容易找到一个数x，（x-1）% MOD == 0 ,就说明这个数是没有逆元的（例217823），那么对于这种情况，我们不能用逆元算，你会发现这种情况下，
pn % MOD == 1 （（p-1）% MOD == 0）），这样（1 + pn + pn2 + ... + pnB*cn） == （1 % MOD + pn %MOD + pn2 %MOD + ... + pnB*cn %MOD） == B*cn+1
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std; const int maxn = 1e4;
const int mod = ;
int a,b;
int p[maxn];
int c[maxn];
int calc(int x)
{
int m= ;
int up = sqrt(x);
for(int i=;i<=up;i++)
{
if(x % i == )p[++m] = i,c[m] = ;
while(x % i == )x/= i,c[m]++;
}
if(x > )p[++m] = x,c[m] = ;
return m;
} typedef long long ll; ll qpow(ll a,ll b)
{
ll ans = ;
ll base = a;
while(b)
{
if(b&)ans = (ans * base)%mod;
base = (base * base)%mod;
b >>= ;
}
return ans;
}
int main()
{
scanf("%d%d",&a,&b);
int n = calc(a);
ll ans = ;
for(int i=;i<=n;i++)
{
if((-p[i])%mod == )
{
ans = (ans * (b * c[i]+ ))%mod;
continue;
}
ll Ni = qpow(-p[i],mod-);
ll tmp = -qpow(p[i],c[i]*b+);
ans = (ans * (tmp*Ni%mod+mod)%mod)%mod;
}
printf("%lld\n",ans);
}
还有一种写法，就是不用公式计算等比数列和，这样就避免了逆元的问题
sum（p，c） = （1 + p + p2 + ... + pk）
（1）c为奇数，sum（p，k）= sum（p，（k-1 ）/2）*（1+p（k+1）/2）
sum（p，c） = （1 + p + p2 + ... + p（k-1）/2）+ （p（k+1）/2 + ... + pk） （c为奇数，加上0次幂，变成偶数，刚好可以分成两个等长的数列）
（2）c为偶数，sum（p，k）= sum（p，k/2-1）*（1+pk/2）+ pk
sum（p，c） = （1 + p + p2 + ... + pk/2-1）+ （pk/2 + ... + pk-1）+ pk （c+1是奇数）
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std; const int maxn = 1e4;
const int mod = ;
int a,b;
int p[maxn];
int c[maxn];
int calc(int x)
{
int m= ;
for(int i=;i*i<=x;i++)
{
if(x % i == )p[++m] = i,c[m] = ;
while(x % i == )x/= i,c[m]++;
}
if(x > )p[++m] = x,c[m] = ;
return m;
} typedef long long ll;
ll qpow(ll a,ll b)
{
ll ans = ;
ll base = a;
while(b)
{
if(b&)ans = (ans * base)%mod;
base = (base * base)%mod;
b >>= ;
}
return ans;
}
ll sum(ll p,ll c)
{
if(c == )return ;
if(c&)return ((+qpow(p,(c+)/))%mod*(sum(p,(c-)/)%mod))%mod;
else return ((+qpow(p,c/))%mod*(sum(p,c/-))%mod+qpow(p,c))%mod;
} int main()
{
scanf("%d%d",&a,&b);
int n = calc(a);
ll ans = ;
for(int i=;i<=n;i++)
{
ans = (ans * sum(p[i],c[i]*b))%mod;
}
printf("%lld\n",ans);
}