莫比乌斯反演

​ 对于两个定义域为非负整数的函数\(F(n)\)和\(f(n)\)

​ 若满足：\(F(n)=\sum\limits_{d|n}f(d)\)，则反演得到\(f(n)=\sum\limits_{d|n}\mu(d)F(\frac n d)\)；

\[ \sum_{d\mid n}\mu(d)F(\frac n d)= \sum_{d\mid n}\mu(d)\sum_{d'\mid (n/d)}f(d')= \sum_{d'\mid n}f(d')\sum_{d|(n/d')}\mu(d)\\ \because根据下文\mu的性质，当且仅当n/d'=1时式子有值，此时d'=n,d=1\\ \therefore原式=f(n)*\mu(1)=f(n) \]

​ 常用变式：若满足：\(F(n)=\sum\limits_{n|d}f(d)\)，则反演得到\(f(n)=\sum\limits_{n|d}\mu(\frac d n)F(d)\) 。

\(\mu(i)\)函数（莫比乌斯函数）

​ 定义：

\[ \mu(d)=\begin{cases} 1& d=1\\ (-1)^k& d=p_1p_2...p_k&(p_i为互异素数)\\ 0& d=p_1p_2...p_k &(p_i为素数，但有重复，即存在平方因子) \end{cases} d\in\mathbb{N}^* \]

​ 按照定义用线性筛来求解：

​ 循环\(i\)，判定\(i\)为素数时，令\(\mu(i)=-1\)；

​ 筛到\(x\)时(\(x=i*p\))，若\(i|p\)，则\(x\)有\(p^2\)这个因子，此时令\(\mu(x)=0\)；

​ 否则\(i\nmid p\)，则\(x\)的互异素数数量加1，则令\(\mu(x)=-\mu(i)\)

mu[1]=1;for(int i=2;i<=n;i++){    if(!vis[i]){        lis[++cnt]=i;        mu[i]=-1;    }    for(int j=1;j<=cnt&&i*lis[j]<=n;j++){        vis[i*lis[j]]=1;        if(i%lis[j]==0){            mu[i*lis[j]]=0;            break;        }        mu[i*lis[j]]=-mu[i];    }}

​ \(\mu(i)\)函数性质：（1）它是积性函数。

​ （2）对于\(n\in\mathbb{N}^*\)：

\[ \sum_{d\mid n}\mu(d)=\begin{cases} 1& n=1\\ 0& else \end{cases} \]

\[ \sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n} \]

求解应用

BZOJ2820 GCD

​ 给定\(n,m\)，求满足\(1\le x\le n,1\le y\le m\) 且 \(gcd(x,y)\)为质数的\((x,y)\)有多少对.

​ 我们设出两个函数，使得它们满足反演变式的关系：\(F(d)\)表示\(d\mid gcd(x,y)\) 的有多少对，\(f(d)\) 表示\(gcd(x,y)=d\)的有多少对，其中\(1\le x\le n,1\le y\le m\).

​ 它们确实满足\(F(n)=\sum\limits_{n|d}f(d)\) . 故\(f(n)=\sum\limits_{n|d}\mu(\frac d n)F(d)\). 方便的是\[F(d)=\lfloor \frac n d\rfloor\lfloor\frac m d \rfloor \]，即每个数对可以看成\((d*x,d*y)\)，然后考虑\(x\)和\(y\)的取值各有多少种，乘起来便是\(F(d)\) ，因此\(f(n)=\sum\limits_{n\mid d }\mu(\frac d n)\lfloor \frac n d\rfloor\lfloor\frac m d \rfloor\).

​

\[ \begin{aligned} ans&=\sum_{p}f(p)\\ &=\sum_{p}\sum_{p\mid d }\mu(\frac d p)\lfloor \frac n d\rfloor\lfloor\frac m d \rfloor\\ &=\sum_p\sum_{k=1}^{\lfloor min(n,m)/p\rfloor}\mu(\frac{kp}p)\lfloor\frac n {kp}\rfloor\lfloor\frac m {kp}\rfloor&枚举d的取值，用kp替代\\ &=\sum_{T=1}^{min(n,m)}\lfloor\frac n T\rfloor\lfloor\frac m T\rfloor\sum_{p\mid T}\mu(\frac T p) &令T=kp \end{aligned} \]

​ 令\(g(x)=\sum_\limits{p\mid x}\mu(\frac x p)\) ，那么现在的任务是求出所有的\(g(x)\). 考虑用线性筛的方式来求:

​ 循环\(i\)， 判定\(i\)是质数时，令\(g(i)=\mu(1)=1\)

​ 筛到\(x\)时(\(x=i*P\))，若\(P\mid i\)，则\(x\)有\(P^2\)这个因子，除非求值式中的\(p\)将\(x\)中的\(P^2\)除去，否则\(\mu(\frac x p)=0\)，唯一一个有值的是当\(p=P\)时\(\mu(\frac x P)=\mu(i)\). 综合，\(g(x)=\mu(i)\)

​ 若\(P\nmid i\)，则\(P\)与\(i\)互质。当\(p=P\)时，值是\(\mu(\frac {iP}P)=\mu(i)\)。

​ 当\(p\ne P\)时，循环的\(p\)和g(i)中循环的\(p\)是一样的 ，则\[且\sum_{p|x且p!=P}\mu(\frac xp)=\sum_{p|i}\mu(\frac i p*P)=\sum_{p|i}\mu(\frac i p)\mu(P)=\mu(P)\sum_{p|i}\mu(\frac ip)=-1*g(i)=-g(i)\]

​ 综合，\(g(x)=\mu(i)-f(i)\)

​ 于是用线性筛求出了\(g(x)\)

​ 回到答案的表达式\(ans=\sum\limits_{T=1}^{min(n,m)}\lfloor\frac n T\rfloor\lfloor\frac m T\rfloor\sum_{p\mid T}\mu(\frac T p)\)，如果循环\(1...min(n,m)\)显然不够快，考虑\(\lfloor\frac n T\rfloor\lfloor\frac m T\rfloor\)的取值是根号级别的，对于每一组\(\lfloor\frac n T\rfloor\lfloor\frac m T\rfloor\)相等的\(l\leq T\leq r\)，可以加快计算，将\(\lfloor\frac n T\rfloor\lfloor\frac m T\rfloor\)提取出来，那么这些\(T\)的贡献就是\(\lfloor\frac n T\rfloor\lfloor\frac m T\rfloor\sum\limits_{i=l}^rg(i)\)，预处理出\(g(i)\)的前缀和即可。

​

#include 
    
     using namespace std;const int N=10000001;typedef long long ll;int T,n,m;int mu[N],g[N];int vis[N],lis[N],cnt;inline void swap(int &x,int &y){int t=x;x=y;y=t;}inline int min(int x,int y){return x
     
      m) swap(n,m);        ll ans=0;        for(int i=1,j;i<=n;i=j+1){            j=min(n/(n/i),m/(m/i));            ans+=1LL*(n/i)*(m/i)*(g[j]-g[i-1]);        }        printf("%lld\n",ans);    }    return 0;}