【CCPC-Wannafly Winter Camp Day3 Div2 F 小清新数论】（莫比乌斯反演）

1.题目链接。这个题目是个反演的题目：

整理之后就简单了，代码如下：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD=998244353;

namespace MOBIUS{
    //最大可用范围[1,maxn),实际使用[1,maxn);
    //初始化要求vis,mu至0,maxn
    const ll maxn=1.1e7;
    ll mu[maxn+10],sum[maxn+10],prime[maxn+10];
    bool vis[maxn+10];
    void mobius_ini(){
        mu[1]=1;
        prime[0]=0;
        for(ll i=2;i<maxn;i++){
            if(!vis[i]){
                mu[i]=-1;
                prime[++prime[0]]=i;
            }
            for(ll j=1;j<=prime[0]&&i*prime[j]<maxn;j++){
                vis[i*prime[j]]=true;
                if(i%prime[j])
                    mu[i*prime[j]]=-mu[i];
                else{
                    mu[i*prime[j]]=0;
                    break;
                }
            }
        }
        for(ll i=1;i<maxn;i++)sum[i]=sum[i-1]+mu[i];
    }
    /*
     01: 1 02:-1 03:-1 04: 0 05:-1 06: 1 07:-1 08: 0 09: 0 10: 1
     11:-1 12: 0 13:-1 14: 1 15: 1 16: 0 17:-1 18: 0 19:-1 20: 0
     21: 1 22: 1 23:-1 24: 0 25: 0 26: 1 27: 0 28: 0 29:-1 30:-1
     31:-1 32: 0 33: 1 34: 1 35: 1 36: 0 37:-1 38: 1 39: 1 40: 0
     41:-1 42:-1 43:-1 44: 0 45: 0 46: 1 47:-1 48: 0 49: 0 50: 0
     51: 1 52: 0 53:-1 54: 0 55: 1 56: 0 57: 1 58: 1 59:-1 60: 0
     61:-1 62: 1 63: 0 64: 0 65: 1 66:-1 67:-1 68: 0 69: 1 70:-1
     71:-1 72: 0 73:-1 74: 1 75: 0 76: 0 77: 1 78:-1 79:-1 80: 0
     81: 0 82: 1 83:-1 84: 0 85: 1 86: 1 87: 1 88: 0 89:-1 90: 0
     91: 1 92: 0 93: 1 94: 1 95: 1 96: 0 97:-1 98: 0 99: 0
     */
    
};


namespace EULER{
    /////////////////////////////////////////////////
    //O(maxn)
    const ll maxn=1.1e7;
    bool vis[maxn+10];
    ll phi[maxn+10],prime[maxn+10];
    ll sum[maxn+10];
    void euler_ini(){
        phi[1]=1;
        ll primes=0;
        for (ll i=2;i<=maxn;i++){
            if(!vis[i]){
                prime[++primes]=i;
                phi[i]=i-1;
                //由函数本身性质推
            }
            for (ll j=1;j<=primes&&i*prime[j]<=maxn;j++){
                vis[i*prime[j]]=true;
                if (i%prime[j])//由积性函数性质推
                    phi[i*prime[j]]=phi[i]*(prime[j]-1);
                else{//找规律
                    phi[i*prime[j]]=phi[i]*prime[j];
                    break;
                }
            }
        }
        
          for(ll i=1;i<maxn;i++)sum[i]=(sum[i-1]+phi[i])%MOD;
    }
};



int main(){
    EULER::euler_ini();
    MOBIUS::mobius_ini();
    ll n;
    while(scanf("%lld",&n)!=EOF){
        ll ans=0;
        for(ll i=1;i<=n;i++){
            ans+=1ll*MOBIUS::mu[i]*(EULER::sum[n/i]*2-1)%MOD + MOD;
            ans%=MOD;
        }
        cout<<ans<<endl;
    }
}