传送门

思路

因数和公式+费马小定理计算乘法逆元。

代码

#include
#define MAXN 9901
using namespace std;
typedef long long LL;
int A, B, ans = 1, res[50];
struct Node { int pri, count; }prime[50];
LL fastpow(LL base, LL top)
{
    LL rel = 1;
    while (top) {
        if (top % 2)
            rel *= base, rel %= MAXN;
        base *= base;
        base %= MAXN;
        top /= 2;
    }
    return rel;
}
int Sum(LL base, LL top)
{
    int res = 0;
    if (base % MAXN == 1) {
        res = 1 + top;
    }
    else {
        res=(fastpow(base,top+1)+MAXN-1)%MAXN*(fastpow(base-1, MAXN - 2)) % MAXN;
    }
    return res % MAXN;
}
int main(void)
{
    cin >> A >> B;
    if (B == 0) {
        cout << 1; return 0;
    }
    int cnt = 0, cop = A;
    for (int i = 2; i<=A; i++)
    {
        if (cop % i == 0) {
            prime[++cnt].pri = i;
            while (cop % i == 0) {
                cop /= i;
                prime[cnt].count++;
            }
            prime[cnt].count *= B;
        }
        if (cop == 1)break;
    }
    for (int i = 1; i <= cnt; i++)
    {
        ans *= Sum(prime[i].pri, prime[i].count);
        ans %= MAXN;
    }
    cout << ans;
    return 0;
}