题解 | #Sumdiv#

首先对于,可以通过质因数分解，求出所有的质因数次数。 对于质因数,次数为，由于次方，那么变为。

约数和可以这样表示：

对于单独的。需要求解这个等差数列的和。由于给出的模数为质数，根据等比数列求和公式。分子下面可以用逆元求得。

还有一种精妙的分治法也可以求得，题解区有就不多赘述，代码中也有体现。

//快速幂
int pow(int x,int n,int m){
    int res = 1;
    while(n){
        if(n & 1) res = res * x % m;
        x = x * x % m;
        n >>= 1;
    }
    return res;
}
//分治法求等比数列和
int f(int p,int n){
    if(n == 0) return 1;
    if(n == 1) return (p + 1) % MOD;
    int res = 0;
    if(n % 2 == 0){
        res += pow(p,n,MOD);
        res %= MOD;
        n--;
    }
    int t = (1 + pow(p,n / 2 + 1,MOD)) * f(p,n / 2) % MOD;
    res += t;
    res %= MOD;
    return res;
}
//逆元求
int f2(int p,int n){
    int inv = pow(1 - p,MOD - 2,MOD);
    return (inv * (1 - pow(p,n + 1,MOD) + MOD)) % MOD;
}
void solve(){
    int a,b; cin >> a >> b;
    if(a == 1 || a == 0){
        cout << "0" << endl;
        return;
    }
    unordered_map<int,int> mp;
    int x = 2;
    while(x * x <= a){
        while(a % x == 0){
            mp[x]++;
            a /= x;
        }
        x++;
    }
    if(a > 1) mp[a]++;
    int res = 1;
    for(auto [p,v]: mp){
        int n = v * b;
        res = (res * f2(p,n)) % MOD;
    }
    cout << (res + MOD) % MOD << endl;
}