描述
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).
输入
The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.
输出
The only line of the output will contain S modulo 9901.
样例输入
2 3
样例输出
15
提示
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).
大概意思是让我们求 (a^b) 的所有因数的和膜9901的值
我们知道在算数基本定理中有 : (a=p_{1}^{c_{1}}*p_{2}^{c_{2}}........*p_{n}^{c_{n}})(第一次用LaTeX)
所以(a^b)的约数和为 ((1+p_{1}+p_{1}^{2}.......+p_{1}^{b*c_{1}})*(1+p_{2}+p_{2}^{2}.......+p_{2}^{b*c_{2}}).....*(1+p_{n}+p_{n}^{2}.......+p_{n}^{b*c_{n}}))
对于上面的每一项我们用等比公式求和
(1+p_{1}+p_{1}^{2}.......+p_{1}^{b*c_{1}}) = (p_{1}^{b*c_{1}+1}-1)/(p_{1}-1)
#include <cstdio>
#include <vector>
typedef long long int ll;
const ll mod=9901;
std::vector<ll> prime;
std::vector<ll> times;
inline void divide(ll n) {
for(ll i=2;i*i<=n;++i) {
if(n%i==0) {
prime.push_back(i);ll cnt=0;
while(n%i==0) {n/=i;++cnt;}
times.push_back(cnt);
}
}
if(n>1) {prime.push_back(n);times.push_back(1);}
}
inline ll qpow(ll n,ll k) {
ll ans=1;
while(k) {
if(k&1) ans=ans*n%mod;
n=n*n%mod;k>>=1;
}
return ans;
}
int main() {
ll a,b;scanf("%lld%lld",&a,&b);
divide(a);
ll ans=1;
for(int i=0,end=prime.size();i<end;++i) {
times[i]*=b;
if((prime[i]-1)%mod==0) ans=ans*(times[i]+1)%mod;
else ans=ans*((qpow(prime[i],times[i]+1)-1+mod)*qpow(prime[i]-1,mod-2)%mod)%mod;
}
printf("%lld
",ans);
return 0;
}