这个B站上的视频讲的不错：

定理：和是定义在非负整数集合上的两个函数，并且满足条件，那么我们得到结论

 

     

 

在上面的公式中有一个函数，它的定义如下：

 

    （1）若，那么

    （2）若，均为互异素数，那么

    （3）其它情况下

 

 

对于函数，它有如下的常见性质：

 

    （1）对任意正整数有

  

                            

 

        （2）对任意正整数有

 

         

         

线性筛选求莫比乌斯反演函数代码：

void Mobius(){    mem(vis,false);    mu[1]=1;    cnt=0;    for(int i=2;i

例题1：

代码：

#include
      
       using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5; int prime[N];bool not_prime[N]={
    false};int mu[N];void Mobius(){    mu[1]=1;    int k=0;    for(int i=2;i
       
        >T;    for(int Case=1;Case<=T;Case++)    {        cin>>a>>b>>c>>d>>k;        if(k==0){            cout<<"Case "<
        
         <<": 0"<
        
       
      

例题2：

代码：

#include
      
       using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5;const int INF=0x3f3f3f3f; const int MOD=1e9+7;int a[N];int prime[N];bool not_prime[N]={
    false};int mu[N];int cnt[2*N];void Mobius(){    mu[1]=1;    int k=0;    for(int i=2;i
       
        >=1;    }    return ans;}int main(){    /*ios::sync_with_stdio(false);    cin.tie(0);*/    int T;    int n;    Mobius();    scanf("%d",&T);    for(int Case=1;Case<=T;Case++)    {        int mn=INF;        int mx=0;        mem(cnt,0);        scanf("%d",&n);        for(int i=1;i<=n;i++)scanf("%d",&a[i]),mn=min(mn,a[i]),mx=max(mx,a[i]);        for(int i=1;i<=n;i++)cnt[a[i]]++;        for(int i=1;i<2*N;i++)cnt[i]+=cnt[i-1];        ll ans=0;        for(int i=2;i<=mn;i++)        {            ll t=1;            for(int j=1;j*i<=mx;j++)            {                t=(t*q_pow(j,cnt[(j+1)*i-1]-cnt[j*i-1]))%MOD;            }            ans=(ans-mu[i]*t%MOD+MOD)%MOD;        }        printf("Case #%d: %lld\n",Case,ans);    }     return 0;}
       
      

例题3：Codeforces 

提示：C(n,2)=n*(n-1)/2=1+2+...+n-1

代码：

#include
      
       using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=5e5+5;const int INF=0x3f3f3f3f; const int MOD=1e9+7;int a[N];int prime[N];bool not_prime[N]={
    false};bool vis[N]={
    false};int mu[N];int cnt[N];void Mobius(){    mu[1]=1;    int k=0;    for(int i=2;i
       
        >n>>q;    for(int i=1;i<=n;i++)cin>>a[i];    ll ans=0;    while(q--)    {        cin>>t;        if(!vis[t])        {            vis[t]=true;            for(int i=1;i*i<=a[t];i++)            {                if(a[t]%i==0)                {                    ans+=(ll)mu[i]*cnt[i];                    cnt[i]++;                    if(i*i!=a[t])ans+=mu[a[t]/i]*cnt[a[t]/i],cnt[a[t]/i]++;                }            }        }        else        {            vis[t]=false;            for(int i=1;i*i<=a[t];i++)            {                if(a[t]%i==0)                {                    cnt[i]--;                    ans-=(ll)mu[i]*cnt[i];                    if(i*i!=a[t])cnt[a[t]/i]--,ans-=mu[a[t]/i]*cnt[a[t]/i];                }            }        }        cout<
        
         <
        
       
      

例题4：大白书P301石头染色方案计数

代码：

 

#include
      
       #include
       
        #include
        
         #include
         
          #include