P1593 因子和 题解

· · 题解

P1593 因子和 题解

结果可能是

\red{负数!}

因为这个我卡在94pts

#include <iostream>//快速幂 + 数学 
using namespace std;//!!可能是负数!!
#define int long long
int MOD = 9901;
const int N = 1e4+10;
int in1,in2,a,b,ans = 1;//一定有1这个因子 
int f[N],cnt[N];
int qpow(int a,int b){
    int res = 1,base = a;
    while(b){
        if(b&1) res = (base * res) % MOD;
        base = (base * base) % MOD;
        b >>= 1; 
    }
    return res;
}
int g(int i){ return qpow(i,MOD-2)%MOD; }
void solve(){
    for(int i = 2;i <= in1;i++){
        if(in1 % i == 0){
            cnt[a] = 0;
            while(in1 % i == 0) cnt[a]++,in1 /= i;
            if(i % MOD == 1) ans = ans * (cnt[a]+1) % MOD;
            else ans = ans * (qpow(i,cnt[a]*in2+1)-1)*g(i-1) % MOD;
        }
    }
}
main(){
    cin >> in1 >> in2;
    solve();
    cout << (ans+MOD)%MOD;
    return 0;
}