关于Mobius反演
欧拉函数 (varphi)(varphi(n)=)表示不超过 (n) 且与 (n) 互质的正整数的个数 线性求 (text{Euler}) 函数: #define int long long int phi[3000005]; int n=3000000; bool mark[3000005]; int prime[1000005]; int tot; void getphi() { phi[1]=1; for(int i=2;i<=n;i++) { if(mark[i]==false) { prime[++tot]=i; phi[i]=i-1; } for(int j=1;j<=tot;j++) { if(i*prime[j]>n) { break; } mark[i*prime[j]]=true; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*phi[prime[j]]; } } for(int i=1;i<=n;i++) { phi[i]+=phi[i-1]; } } (text{Mobius})函数 (mu(n))[ mu(n)= begin{cases} 1&n=1 0&ntext{ 含有平方因子} (-1)^k&ktext{ 为 }ntext{ 的本质不同质因子个数} end{cases} ] 其中 (displaystylevarepsilon(n)=sum_{dmid n}mu(d)) 即 (varepsilon=mu*1) 设 (displaystyle n=prod_{i=1}^k{p_i}^{c_i},n‘=prod_{i=1}^k p_i) 那么 (displaystylesum_{dmid n}mu(d)=sum_{dmid n‘}mu(d)=sum_{i=0}^k C_k^icdot(-1)^k) 根据二项式定理,易知该式子的值在 (k=0) 即 (n=1) 时值为 (1) 否则为 (0) ,这也同时证明了 (displaystylesum_{dmid n}mu(d)=[n=1]) #define int long long int mu[3000005]; int n=3000000; bool mark[3000005]; int prime[1000005]; int tot; void getmu() { mu[1]=1; for(int i=2;i<=n;i++) { if(mark[i]==false) { prime[++tot]=i; mu[i]=-1; } for(int j=1;j<=tot;j++) { if(i*prime[j]>n) { break; } mark[i*prime[j]]=true; if(i%prime[j]==0) { mu[i*prime[j]]=0; break; } mu[i*prime[j]]=-mu[i]; } } } (text{Dirichlet})卷积(text{ID}:text{ID(i)=i}) 莫比乌斯反演公式:设 (f(n),g(n)) 为两个数论函数。 同时,还有另一种(text{Mobius})反演: 柿子简化[sum_{i=1}^{n}{[gcd(i,n)==d]} ] (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |