2019ICPC 银川 D.Easy Problem(反演)

Easy Problem

当时现场赛因为题我推的公式，化简的时候，出现了这个错误，导致找bug找了2个小时。
A掉之后已经没有时间写题了，学了这么久的数论，题真的是再简单不过的反演了，但是策略有问题，加上化简公式时出现的错误，没来的及写，真的很可惜。

最后用欧拉降幂，线性筛即可。

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
using namespace std;
const int N=1e5+5;
const int mod=59964251;
typedef long long ll;
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
const int p=59870352;
char s[N];
ll f[N];
short int mu[N];
int prime[N],tot=0;
bool vis[N];
void pre(int k){
    me(vis,0);tot=0;
    mu[1]=1;f[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i])prime[++tot]=i,mu[i]=-1,f[i]=ksm(i,k,mod);
        for(int j=1;j<=tot&&i*prime[j]<N;j++){
            vis[i*prime[j]]=1;
            f[i*prime[j]]=f[i]*f[prime[j]]%mod;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<N;i++)f[i]=(f[i-1]+f[i])%mod;
}
int main(){
    int T;cin>>T;
    while(T--){
        int m,d,k;
        sc("%s%d%d%d",s,&m,&d,&k);
        pre(k);
        bool flag=0;
        ll n=0;
        for(int i=0;s[i];i++){
            n=n*10+s[i]-'0';
            if(n>p)n%=p,flag=1;
        }
        ll ans=0;
        for(int t=1;t<=m/d;t++){
            if(flag){
                ll x=mu[t]*ksm(t*d,n*k%p+p,mod);
                x=x*ksm(f[m/(d*t)],n+p,mod)%mod;
                ans+=x;
                ans=(ans%mod+mod)%mod;
            }else{
                ll x=mu[t]*ksm(t*d,n*k,mod);
                x=x*ksm(f[m/(d*t)],n,mod)%mod;
                ans+=x;
                ans=(ans%mod+mod)%mod;
            }
        }
        printf("%lld\n",ans);
    }
}