#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=9901;
const ll maxn=100010;
 
ll cnt;
ll ans=1,prime[maxn],prime_cnt[maxn];

ll qpow(ll q,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1){ ans=ans*q%mod; }
        n>>=1; q=q*q%mod; 
    }
    return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(a==0&&b==0) return -1ll;
    if(b==0){ x=1ll,y=0ll; return a; }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x; return d;
}
ll inverse(ll a,ll p)
{
    if(a%p==0) return 1ll;
    else if((a+1)%p==0) return -2ll;
    ll x,y,d=exgcd(a,p,x,y);
    if(d==1) return (x%p+p)%p;
    return -1ll;
}
/*
ll inverse(ll x,ll p) { return qpow(x, mod - 2); }
*/
int main()
{
    ll a,b; cin>>a>>b;
    if(a==0) { cout<<0<<endl; return 0; }
    if(b==0||a==1) { cout<<1<<endl; return 0; }
    for(ll i=2;i*i<=a;i++)
    {
        if(a%i==0)
        {
            prime[++cnt]=i%mod;
            while(a%i==0){ a/=i; prime_cnt[cnt]++; }
        }
    }
    if(a!=1){ prime[++cnt]=a; prime_cnt[cnt]=1; }
    for(ll i=1;i<=cnt;i++)
    {
        if(prime[i]%mod==1){ ans=ans*(prime_cnt[i]+1)%mod; }
        else
        {
            ll div=(prime[i]-1+mod)%mod;
            ans=ans*(qpow(prime[i],prime_cnt[i]*b+1)%mod-1+mod)%mod*inverse(div,mod)%mod;
        }
    }
    cout<<ans<<endl; return 0;
}

• Re:大佬求助（洛谷P1593）已过，POJ wa掉 (1563) hxqasd 2022-09-15 17:19:25