莫比乌斯

一：莫比乌斯函数

定义：μ 为莫比乌斯函数，定义为

[mu left ( n ight )=left{egin{matrix}
1 & n=1 \
0& n含有平方因子\
left ( -1 ight ) ^{k} & n=p_{1}p_{2}p_{3}cdots p_{k}
end{matrix} ight.]

性质1：

[sum_{d|n}mu left ( d ight )=left{egin{matrix}
1 & n=1\
0 & n eq 1
end{matrix} ight.]

即(sum_{d|n}mu left ( d ight )=varepsilon left ( n ight ))，即(mu *1 = varepsilon)

性质2：

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

反演结论：

[left [ gcdleft ( i,j ight )=1 ight ]Leftrightarrow sum_{d|gcdleft ( i,j ight )}mu left ( d ight )]

根据定义：线性筛莫比乌斯函数

 1 bool prime[maxn];
 2 int Prime[maxn],mu[maxn],tot;
 3 void get_mu(){
 4     memset(prime,true,sizeof(prime));
 5     prime[0]=prime[1]=false;
 6     tot=0;
 7     
 8     mu[1]=1;
 9     for(int i=2;i<=n;i++){
10         if( prime[i] ) Prime[++tot]=i,mu[i]=-1;
11         for(int j=1;j<=tot&&i*Prime[j]<=n;j++){
12             prime[i*Prime[j]]=false;
13             if( i%Prime[j]==0 ){
14                 mu[i*Prime[j]]=0;
15                 break;
16             }
17             mu[i*Prime[j]]=-mu[i];
18         }
19     }
20 }

二：莫比乌斯反演

约数公式：

设 (fleft ( n ight ),gleft ( n ight )) 为两个数论函数

如果有[fleft ( n ight )=sum_{d|n}gleft ( d ight )]

那么有[gleft ( n ight )=sum_{d|n}mu left ( d ight )fleft ( frac{n}{d} ight )]

证明：已知(f=g*1)，则(f*mu =g*1*mu Rightarrow f*mu =gleft ( 其中1*mu =varepsilon ight ))

倍数公式：

设 (fleft ( n ight ),gleft ( n ight )) 为两个数论函数

如果有[fleft ( n ight )=sum_{n|d}gleft ( d ight )]

那么有[gleft ( n ight )=sum_{n|d}mu left ( frac{d}{n} ight )fleft ( d ight )]