模意义下的运算
对于一个数 (N) 来说,可以分解成 $$N=p_1 ^ {c_1}p_2^{c_2}cdots P_m ^ {c_m}$$
(N) 的所有正约数的和可表示为:
[(1 + p_1 + p_1 ^2 + cdots p_1 ^ {c_1})* cdots *(1 + p_m + p_m ^2 + cdots + p_m ^{c_m}) = prod_{i =1}^1(sum_{j = 1}^{c_1}(p_j)^i)
]
对于 (N^B) 来说,所有正约数的和可表示为:
[$$(1 + p_1 + p_1 ^2 + cdots p_1 ^ {c_1 * B})* cdots *(1 + p_m + p_m ^2 + cdots + p_m ^{c_m * B}) = prod_{i =1}^1(sum_{j = 1}^{c_j * B}(p_j)^i)
]
那么对于每个质因数来说都是一个等差数列求和,运用等差数列求和公式做即可,对于除法来说,转换为乘上他的逆元, 因为 9901 是一个质数,所以对于 (P_i - 1)这个数来说,如果他不是 9901 的倍数,那么他就有逆元, 如果他是倍数,等差数列的公比就变为了 1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define ll long long
using namespace std;
const int MOD = 9901;
ll Qfactor[100][2], tot, A, B, ans = 1ll;
void divide(ll n) {
for(ll i = 2; i * i <= n; i++) {
if(!(n % i)) {
Qfactor[++tot][0] = i;
while(!(n % i)) {Qfactor[tot][1]++; n /= i;}
}
}
if(n > 1) {Qfactor[++tot][0] = n; Qfactor[tot][1] = 1;}
}
ll quick_mod(ll n, ll k) {
ll ans = 1;
while(k) {
if(k & 1ll) (ans *= n) %= MOD;
(n *= n) %= MOD;
k >>= 1;
}
return ans;
}
int main() {
cin>>A>>B;
divide(A);
for(int i = 1; i <= tot; i++) {
if(!((Qfactor[i][0] - 1) % MOD)) (ans *= Qfactor[i][1] * B + 1) %= MOD;
else {
(ans *= (quick_mod(Qfactor[i][0], Qfactor[i][1] * B + 1) - 1 + MOD) % MOD) %= MOD;
(ans *= quick_mod(Qfactor[i][0] - 1, MOD - 2)) %= MOD;
}
}
cout<<ans<<endl;
return 0;
}