AcWing 97. 约数之和 公式法
原题链接
中等
作者:
Snrise
,
2024-04-07 21:10:56
,
所有人可见
,
阅读 3
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int MOD = 9901;
int a, b;
int mod(int a,int b)
{
return (a % b + b) % b;
}
int qmi(int a, int n)
{
int res = 1;
while (n)
{
if (n & 1)
{
res = res * a % MOD;
}
a = a * a % MOD;
n >>= 1;
}
return res % MOD;
}
signed main(void)
{
cin >> a >> b;
if (a == 0)
{
cout << 0 << endl;
return 0;
}
int ans = 1;
for (int i = 2; i <= a / i; i++)
{
if (a % i == 0)
{
int k = 0;
while (a % i == 0)
{
a /= i;
k++;
}
k *= b;
// 如果分母不存在对MOD的模意义下的乘法逆元;
if ((i - 1) % MOD == 0)
{
// i % MOD = 1;
// i^0 % MOD + i^1 % MOD + ... + i^k % MOD= k + 1;
ans = ans * (k + 1) % MOD;
}
else
{
ans = (ans * (qmi(i, k + 1) - 1) % MOD * qmi(i - 1, MOD - 2) % MOD) % MOD;
}
}
}
if (a > 1)
{
int k = b;
if ((a - 1) % MOD == 0)
{
ans = ans * (k + 1) % MOD;
}
else
{
ans = (ans * (qmi(a, k + 1) - 1) % MOD * qmi(a - 1, MOD - 2) % MOD) % MOD;
}
}
cout << mod(ans, MOD) << endl;
return 0;
}