G13 同余式 乘法逆元 费马小定理

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL p=9901;
LL qpow(LL a,LL b)
{
    LL ret=1%p;a%=p;
    for(;b;b>>=1)
    {
        if(b & 1) ret=(ret*a)%p;
        a=(a*a)%p;
    }
    return ret;
}
int main()
{
    LL ans=1,a,b; 
    scanf("%lld%lld",&a,&b);
    for(LL i=2;i<=a;i++)if(a%i==0)
    {
        LL t=0;
        while(a%i==0) a/=i,t++;
		t*=b;
        ans=( ans*(qpow(i,t+1)-1)*qpow(i-1,p-2)  )%p;
    }
    printf("%lld\n",ans);
    return 0;
}

G13 同余式 乘法逆元 费马小定理

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL p=9901;
LL qpow(LL a,LL b)
{
    LL ret=1%p;a%=p;
    for(;b;b>>=1)
    {
        if(b & 1) ret=(ret*a)%p;
        a=(a*a)%p;
    }
    return ret;
}
int main()
{
    LL ans=1,a,b; 
    scanf("%lld%lld",&a,&b);
    for(LL i=2;i<=a;i++)if(a%i==0)
    {
        LL t=0;
        while(a%i==0) a/=i,t++;
		t*=b;
        ans=( ans*(qpow(i,t+1)-1)*qpow(i-1,p-2)  )%p;
    }
    printf("%lld\n",ans);
    return 0;
}