XCPC中的莫比乌斯反演

D. Easy Problem

From:The 2019 ICPC Asia Yinchuan Regional Contest

solutions

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=59964251,N=1e5+10;
int pmod;
int qpow(int b,int p=mod-2){
    if(p>=pmod) p=p%pmod+pmod;
    int res=1;
    while(p){
        if(p&1) res=res*b%mod;
        p>>=1;
        b=b*b%mod;
    }
    return res;
}
int get_phi(int n){
    int res=n;
    for(int i=2;i<n/i;i++){
        if(n%i==0){
            while(n%i==0) n/=i;
            res=res*(i-1)/i;
        }
    }
    if(n) res=res*(n-1)/n; 
    return res;
}
string b;
int n;
int depow(int phi){
    int flag=0,res=0;
    for(int i=0;i<b.size();i++){
        res=res*10+b[i]-'0'; 
        if(res>phi) flag=1,res%=phi;
    }
    if(flag) res+=phi;
    return res;
}
int powk[N];
int p[N],vis[N],mu[N],cnt;
void get_mu(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            p[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;i<=n/p[j];j++){
            int m=i*p[j];
            vis[m]=1;
            if(i%p[j]==0){
                mu[m]=0;
                break;
            }
            else mu[m]=-mu[i];
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    pmod=get_phi(mod);
    get_mu(N-10);
    while(t--){
        int m,d,k;
        cin>>b>>m>>d>>k;
        for(int i=1;i<=m;i++) powk[i]=(qpow(i,k)+powk[i-1])%mod;
        n=depow(pmod);
        m/=d;
        int ans=0;
        for(int i=1;i<=m;i++){
            ans+=(mu[i]*qpow(i,n*k))%mod*qpow(powk[m/i],n)%mod;
            ans=(ans+mod)%mod;
        }
        cout<<ans*qpow(d,n*k)%mod<<'\n';
    }
    return 0;
}

H - Curious

From:The 14th Jilin Provincial Collegiate Programming Contest

solutions

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N],sum[N],g[N];
int p[N],vis[N],mu[N],cnt;
void get_mu(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            p[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;i<=n/p[j];j++){
            int m=i*p[j];
            vis[m]=1;
            if(i%p[j]==0){
                mu[m]=0;
                break;
            }
            else mu[m]=-mu[i];
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    get_mu(N-10);
    while(t--){
        int n,m,k;
        cin>>n>>m>>k;
        for(int i=1;i<=m;i++) sum[i]=g[i]=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum[a[i]]++;
        }
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j+=i){
                g[i]+=sum[j];
            }
        }
        while(k--){
            int x;
            cin>>x;
            int ans=0;
            for(int i=1;i<=m/x;i++){
                ans+=mu[i]*g[i*x]*g[i*x];
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}