逆元暴力

先唯一分解定理分解一下a，根据某推论，约数之和是$ \prod_{i = 1}^{n} \sum_{j = 0}^{ci}p_{i}^{j}$

连乘中每一项都是等比数列，9901是质数，除法直接逆元代替

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
ll m = 9901;
ll ksm(ll n, ll k)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = (res * n) % m;
        n = (n * n) % m;
        k >>= 1;
    }
    return res % m;
}
void solve(ll i, ll &ans)
{
    if(a % i == 0)
    {
        ll cnt = 0;
        while(a % i ==0)
        {
            a /= i;
            cnt ++;
        }
        cnt *= b;
        if((i - 1) % m == 0)
        {
            ans *= cnt + 1;
            ans %= m;
        }
        else
        {
            ll inv = ksm(i - 1, m - 2);
            ans *= ((((ksm(i, cnt + 1) - 1) + m) % m) * inv) % m;
            ans %= m;
        }
    }
}
int main()
{
    cin >> a >> b;
    if(a == 0){cout<<0;return 0;}
    ll ans = 1;
    for(ll i = 2; i * i <= a; i++)
    {
        solve(i,ans);
    }
    if(a > 1) solve(a,ans);
    cout<<ans;
}