tyiii @ 2024-03-29 11:40:38
#include <bits/stdc++.h>
using namespace std;
struct {
int prime, cnt;
}p[25];
int a, b, ans, siz, sum[25];
const int mod = 9901;
bitset<7072>che;
int prime[908], top;
void euler() {
for (int i = 2; i <= 7071; ++i) {
if (!che.test(i)) {
prime[++top] = i;
}
for (int j = 1; j <= top && prime[j] * i <= 7071; ++j) {
che.set(prime[j] * i);
if (i % prime[j] == 0) break;
}
}
}
int ModExpFast(int a, int n, int m) {//快速幂取模
int res = 1;
a = a % m;
while (n) {
if ((n & 1) == 1)
res = (res * a) % m;
a = (a * a) % m;
n = n >> 1;
}
return res;
}
int main() {
cin >> a >> b;
euler();
for (int i = 1; i <= top; ++i) {
if (a % prime[i] == 0) p[++siz].prime = prime[i];
while (a % prime[i] == 0) {
p[siz].cnt += b;
a /= prime[i];
}
}
if (a != 1) {
p[++siz].prime = a;
p[siz].cnt = 1;
}//生成质因子表
for (int i = 1; i <= siz; ++i) {
int pr = p[i].prime, n = p[i].cnt;
if ((pr - 1) % mod == 0) {
sum[i] = 1 + n;
}
else {
sum[i] = (((ModExpFast(pr, n + 1, mod) - 1 + mod) % mod) * ModExpFast(pr - 1, mod - 2, mod)) % mod;
}
}
ans = 1;
for (int i = 1; i <= siz; ++i) {
ans = (ans * sum[i]) % mod;
}
cout << ans;
return 0;
}