莫比乌斯反演练习bzoj2440；bzoj2301；bzoj2820 YY的GCD

预备知识：

1. 莫比乌斯函数

1.1 莫比乌斯函数

$\mu (n) = \begin{cases} 1 & n=1\\ (-1)^k & n=p_1p_2 \cdots p_k，质因子指数均为1且互不相同 \\ 0 & 其余情况\\ \end{cases}$

1.2 莫比乌斯函数的性质

$\sum_{d|n} \mu(d) = (n==1)$

证明略。。
#### $1.3$ 实现方法
线性筛。
线性筛法求素数的过程，每求出一个素数 $p$ ， $mu[p] = -1$ ;
筛非素数的过程，要break的地方， $mu[i*prime] = 0$ ;(因为它有幂数大于1的质因子)；否则 $mu[i*prime] = -mu[i]$ ;

void getmu(){
    cnt=0;mu[1]=1;
    for(int i=2;i<N;i++){
        if(!p[i]){
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&prime[j]*i<N;j++){
            p[prime[j]*i]=1;
            if(i%prime[j]==0){
                mu[prime[j]*i]=0;
                break;
            }
            mu[prime[j]*i]=-mu[i];
        }
    }
}

2. 莫比乌斯反演

2.1 莫比乌斯反演定理

$F(n)=\sum_{d|n} f(d) \Rightarrow f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})$
或者另一种形式为 $F(n)=\sum_{n|d}f(d) \Rightarrow f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)$
第二个比较常用。

2.1 莫比乌斯反演定理的证明

https://www.zhihu.com/question/23764267/answer/26007647
popoqqq也给出了一个证明。大体思想和上类似。不过还是觉得狄利克雷卷积看着更清爽。

2.2 莫比乌斯反演定理的应用

popoqqq-莫比乌斯反演
约数和与倍数和。

3. 习题

(题解基本都抄自POPOQQQ，感谢。)

$3.1$ bzoj2440: [中山市选2011]完全平方数

$3.1.1$ 题目描述

求第k个不含有平方因子的数。多组数据。 $T\leq50, k \leq 10^9$

$3.1.2$ 题目分析

首先二分答案问题转化为求 $[1,x]$ 之间有多少个无平方因子数。
根据容斥原理可知对于sqrt(x)以内所有的质数有
x以内的无平方因子数
=0个质数乘积的平方的倍数的数的数量(1的倍数)
-每个质数的平方的倍数的数的数量(9的倍数,25的倍数,...)
+每2个质数乘积的平方的倍数的数的数量(36的倍数,100的倍数,...)-...
容易发现每个乘积a前面的符号恰好是 $\mu(a)$ (例如 $\mu(3)=-1$ ，故9对答案的贡献为负； $\mu(6)=1$ ，故36对答案的贡献为正) $x$ 以内 $i^2$ 的倍数有 $\lfloor\frac{x}{i^2}\rfloor$ 个故有 $Q(x)=\sum_{i=1}^{\sqrt x}\mu(i)*\lfloor\frac{x}{i^2}\rfloor$
这题和莫比乌斯反演没关系，算是莫比乌斯函数的一个应用吧。。。

#include<cstdio>
#include<cmath>
#define ll long long
#define N 50005
using namespace std;
bool p[N]={1,1};
int prime[N],mu[N],cnt;
int t,n;
void getmu(){
    cnt=0;mu[1]=1;
    for(int i=2;i<N;i++){
        if(!p[i]){
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&prime[j]*i<N;j++){
            p[prime[j]*i]=1;
            if(i%prime[j]==0){
                mu[prime[j]*i]=0;
                break;
            }
            mu[prime[j]*i]=-mu[i];
        }
    }
}
bool judge(ll x){
    int l=sqrt(x),ret=0;
    for(int i=1;i<=l;i++)
        ret+=x/i/i*mu[i];
    return ret>=n;
}
int main(){
    getmu();
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        ll l=0,r=n+n+1;
        while(l<r){
            ll mid=(l+r)/2;
            if(judge(mid)) r=mid;
            else l=mid+1;
        }
        printf("%lld\n",l);
    }
    return 0;
}

$3.2$ bzoj2301: [HAOI2011]Problem b

$3.2.1$ 题目描述

n次询问，每次询问有多少个数对 $(x,y)$ 满足 $a\leq x\leq b,c\leq y\leq d且gcd(x,y)=k$ $N\leq50000,1\leq a\leq b\leq 50000,1\leq c\leq d\leq 50000$
##### $3.2.2$ 题目分析
首先利用容斥原理将一个询问拆分成四个，每次询问有多少个数对(x,y)满足1<=x<=n,1<=y<=m且gcd(x,y)=k
这个问题等价于询问有多少个数对(x,y)满足1<=x<= $\lfloor \frac{n}{k}\rfloor$ ,1<=y<= $\lfloor \frac{m}{k}\rfloor$ 且gcd(x,y)=1
由于之前的结论，我们可以令f(i)为1<=x<=n,1<=y<=m且gcd(x,y)=i的数对(x,y)的个数，F(i)为1<=x<=n,1<=y<=m且i|gcd(x,y)的数对(x,y)的个数。(倍数和。)
我们求 $f(1)$
那么显然有 $F(i)=\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor$
反演后得 $f(i)=\sum_{i|d}\mu(\frac{n}{d})F(d)=\sum_{i|d}\mu(\frac{d}{i})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$
枚举原题中k的每一个倍数，我们就可以O(n)时间处理每个询问了
但是O(n)还是不能胜任本题的数据范围
考虑进一步优化
观察式子，发现 $\lfloor\frac{n}{i}\rfloor$ 最多有 $2\sqrt n$ 个取值
那么 $\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor$ 就至多有 $2\sqrt n+2\sqrt m$ 个取值
枚举这 $2\sqrt n+2\sqrt m$ 个取值，对莫比乌斯函数维护一个前缀和，就可以在 $O(n\sqrt n)$ 时间内出解
总时间复杂度
枚举除法的取值这种方法在莫比乌斯反演的应用当中非常常用，且代码并不难写

#include<cstdio>
#include<algorithm>
#define N 50005
#define ll long long
using namespace std;
bool p[N]={1,1};
int prime[N],mu[N],sum[N],cnt,t,a,b,c,d,k;
void getmu(){
    mu[1]=1;cnt=0;
    for(int i=2;i<N;i++){
        if(!p[i]){
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<N;j++){
            p[i*prime[j]]=1;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<N;i++) sum[i]=sum[i-1]+mu[i];
    //for(int i=1;i<100;i++) printf("%d\n",mu[i]);
}
ll getans(int n,int m){
    ll ret=0;
    if(n>m) swap(n,m);
    for(int i=1,last;i<=n;i=last+1){
        last=min(n/(n/i),m/(m/i));
        ret+=(ll)(n/i)*(ll)(m/i)*(ll)(sum[last]-sum[i-1]);
    }
    return ret;
}
int main(){
    scanf("%d",&t);
    getmu();
    for(int i=1;i<=t;i++){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        printf("%lld\n",getans(b/k,d/k)-getans((a-1)/k,d/k)-getans(b/k,(c-1)/k)+getans((a-1)/k,(c-1)/k));
    }
    return 0;
}

$3.3$ bzoj2820 YY的GCD

$3.3.1$ 题目描述

求有多少数对(x,y)(1<=x<=n,1<=y<=m)满足gcd(x,y)为质数
n,m<= $10^7$ 数据组数<=10000
##### $3.3.2$ 题目分析
根据上一题，我们枚举每一个质数那么答案就是 $ans=\sum_{isprime(p)}^{min(n,m)}\sum_{d=1}^{min(n,m)}\mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor$
直接做显然TLE 考虑优化
令 $T=pd$ ，那么有 $ans=\sum_{T=1}^{min(n.m)}\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor\sum_{p|T}\mu(\frac{T}{p})$
和上题的式子很像。我们如果求出 $\sum_{p|T}\mu(\frac{T}{p})$ 的前缀和，也就可以 $O(\sqrt n)$ 的时间内求解了。
枚举每个素数，更新它的倍数。复杂度 $O(n)$ 。

#include<cstdio>
#include<algorithm>
#define N 10000005
#define ll long long
using namespace std;
ll ans;
int prime[N],mu[N],cnt,a[N],T,n,m;
bool p[N]={1,1};
void getmu(){
    mu[1]=1;
    for(int i=2;i<N;i++){
        if(!p[i]){
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&prime[j]*i<N;j++){
            p[i*prime[j]]=1;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
}
void init(){
    for(int i=1;i<=cnt;i++)
        for(int j=1;j*prime[i]<N;j++)
            a[prime[i]*j]+=mu[j];
    for(int i=1;i<N;i++) a[i]=a[i-1]+a[i];
}
void getans(int n,int m){
    ans=0;
    if(n>m) swap(n,m);
    for(int i=1,last;i<=n;i=last+1){
        last=min(n/(n/i),m/(m/i));
        ans+=(ll)(n/i)*(m/i)*(a[last]-a[i-1]);
    }
}
int main(){
    getmu();
    init();
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        getans(n,m);
        printf("%lld\n",ans);
    }
    return 0;
}

更后话：
以及自己不会反演啊怎么破눈_눈。