莫比烏斯函數定義
μ(n)=⎧⎩⎨⎪⎪1(−1)k0(n=0)(n=p1p2...pk,∀pi!=pj)(others) μ ( n ) = { 1 (n=0) ( − 1 ) k ( n = p 1 p 2 . . . p k , ∀ p i ! = p j ) 0 ( o t h e r s )
莫比烏斯函數計算
直接計算,隻需要對n做一次唯一分解就可以了,複雜度 O(n−−√) O ( n )
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int main(){
int n,m,k;
while(scanf("%d",&n)==){
m=sqrt(n)+;
k=;
bool ok=true;
for(int i=;i<=m;++i){
if(n%i==){
int tmp=;
while(n%i==){
n/=i;
++tmp;
}
if(tmp>){
ok=false;
break;
}
else k+=tmp;
}
}
if(n>) ++k;
if(ok) printf("%d\n",(k&)?-:);
else puts("0");
}
return ;
}
線性篩選
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
bool vis[maxn];
int prim[maxn];
int mu[maxn];
int cnt;
void get_mu(int n){
mu[]=;
for(int i=;i<=n;i++){
if(!vis[i]){
prim[++cnt]=i;
mu[i]=-;
}
for(int j=;j<=cnt && prim[j]*i<=n;j++){
vis[prim[j]*i]=;
if(i%prim[j]==) break;
else mu[i*prim[j]]=-mu[i];
}
}
}
莫比烏斯函數的常用性質
∑d|nμ(d)={10(n=1)(其它) ∑ d | n μ ( d ) = { 1 (n=1) 0 ( 其 它 )
∑d|nμ(d)d=phi(n)n ∑ d | n μ ( d ) d = p h i ( n ) n
反演公式
對于函數 F(n) F ( n ) 和 f(n) f ( n ) 滿足
F(n)=∑d|nf(d) F ( n ) = ∑ d | n f ( d )
那麼就有 f(n)=∑d|nu(d)F(nd) f ( n ) = ∑ d | n u ( d ) F ( n d )
或者若滿足 F(n)=∑n|df(d) F ( n ) = ∑ n | d f ( d )
就有 f(n)=∑n|du(dn)F(d) f ( n ) = ∑ n | d u ( d n ) F ( d )