链接:
https://www.acwing.com/problem/content/99/
题意:
假设现在有两个自然数A和B，S是AB的所有约数之和。
请你求出S mod 9901的值是多少。
思路:
考虑a^b次方的约数可以变为对a进行质数分解,对每个指数的次数乘上b.就构成了a^b的约数集合.
同时求和就是每个质数的组合.可以变成对每个质数求起0次到k次的和,将每个和相乘.
求0次到k次的和时可以用分治,将一个和分成两半来求.
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 9901;
int a, b;
LL QuickPow(LL a, LL b)
{
LL res = 1;
while (b)
{
if (b&1)
res = (res*a)%MOD;
b >>= 1;
a = (a*a)%MOD;
}
return res;
}
LL Sum(LL p, LL c)
{
if (c == 0)
return 1LL;
if (c%2 == 0)
return (((1LL+QuickPow(p, c/2)) * Sum(p, c/2-1))%MOD+QuickPow(p, c))%MOD;
else
return ((1LL+QuickPow(p, (c+1)/2))*Sum(p, c/2))%MOD;
}
int main()
{
// cout << Sum(2, 3) << endl;
scanf("%d%d", &a, &b);
LL res = 1;
for (int i = 2;i <= a;i++)
{
int cnt = 0;
while (a%i == 0)
{
cnt++;
a/=i;
}
if (cnt)
res = res*Sum(i, cnt*b)%MOD;
}
if (a == 0)
printf("0\n");
else
printf("%lld\n", res);
return 0;
}