传送门
以下定理参考博客
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 9901; ll a, b; ll ksm(ll x, ll y) { ll ans = 1; x%=mod; while(y) { if(y&1) ans = (ans*x)%mod; x = (x*x)%mod; y >>= 1; } return ans%mod; } ll work(ll p, ll k) ///计算(p^0+p^1+....+p^k) { if(k == 0) return 1; if(k%2 == 1) return (1+ksm(p, k/2+1))*work(p, k/2)%mod; else return (1+p*(work(p, k-1)))%mod; } int main() { scanf("%lld%lld", &a, &b); ll ans = 1; for(ll i = 2; i*i <= a; ++i) { while(a%i == 0) { ll c = 0; while(a%i == 0) c++, a/=i; ans = (ans*work(i, b*c))%mod; } } if(a > 1) ans = (ans*work(a, b))%mod; if(a == 0) ans = 0; ///a等于0的时候特判答案为0 printf("%lld\n", ans); return 0; }