參考1
參考2
參考3

問題引入：

入門題
給定N和M和D，求滿足1<=x<=N,1<=y<=M且gcd(x,y)=D的點對(x,y)的個數(shù)
1<=N,M<=1000000

莫比烏斯函數(shù)

μ
μ(n) = 1 , n=1
μ(n) = (-1)^k, n=p1 * p2 * … * Pk
（x有奇數(shù)個質(zhì)因子時為-1，x有偶數(shù)個質(zhì)因子時為1）
μ(n) = 0 其他情況（x存在平方因子）

莫比烏斯線性篩：

int prime[MAXN],prime_tot; bool prime_tag[MAXN]; int mu[MAXN]; void pre_calc(int lim) {mu[1]=1;for(int i=2;i<=lim;i++){if(!prime_tag[i]){prime[++prime_tot]=i;mu[i]=-1;}for(int j=1;j<=prime_tot;j++){if(i*prime[j]>lim)break;prime_tag[i*prime[j]]=1;if(i%prime[j]==0){mu[i*prime[j]]==0;break;}else {mu[i*prime[j]]=-mu[i];}}}}

狄利克雷卷積介紹

狄利克雷卷積：( f * g )(n) = ∑_d|nf(d)g(n/d)
d是n的因子
積性函數(shù)是指一個定義域為正整體n的算術(shù)函數(shù)f(n)
積性函數(shù)：對于任意互質(zhì)的整數(shù)a和b有性質(zhì)f(ab)=f(a)f(b)的函數(shù)
完全積性函數(shù)：對于任意整數(shù)a和b有性質(zhì)f(ab)=f(a)f(b)的函數(shù)
若n = p1^a1 *p2^a2 * … * pk^ak
則 f(n) = f(p1^a1) *f(p2^a2) * … * f(pk^ak)
常見的積性函數(shù)：
歐拉函數(shù)： φ(n)
n=∑_i/nφ(i)
莫比烏斯函數(shù)：μ(n)
單位函數(shù)：Id(n)=n
不變函數(shù)：1(n)=1
冪函數(shù)：Idk(n)=n^k
因子個數(shù)函數(shù)：d(n),d= 1 * 1
因子和函數(shù)：σ(n),σ=1 * Id
因子函數(shù)：σk(n)
狄利克雷卷積單位元：ε = [n==1]
（當(dāng)n=1時，ε=1，否則等于0）
μ * 1 = ε

莫比烏斯反演

解決問題：

[a’/d]（向下取整）在一段區(qū)間內(nèi)并不變化，所以最多取到2√a’
按照取值將O（√n）段，對μ（d）計算前綴和，然后計算即可
參考練習(xí)

代碼：

#include <cstdio> #include <algorithm> #include <cstring> using namespace std;const int N=1e5+5; int p[N+10],check[N+10],tot; int mu[N],sum[N]; int T,n,m,d,ans;void init(){memset(check,1,sizeof check);mu[1]=1;for(int i=2;i<=N;i++){if (check[i]){p[++tot]=i;mu[i]=-1;}for (int j=1;j<=tot && p[j]*i<=N;j++){check[i*p[j]]=0;if (i%p[j]==0){mu[i*p[j]]=0;break; }else mu[i*p[j]]=-mu[i];}}for(int i=1;i<=N;i++)sum[i]=mu[i]+sum[i-1]; //維護(hù)前綴和 }int calc(int n,int m){ //求[1,n][1,m]區(qū)間內(nèi)互質(zhì)的(x,y)的對數(shù)int ret=0;if (n>m) swap(n,m);for (int L=1,R=0;L<=n;L=R+1){R=min(n/(n/L),m/(m/L)); // 分段ret+=(sum[R]-sum[L-1])*(n/L)*(m/L);}return ret; }int main(){init();scanf("%d",&T);while (T--){scanf("%d%d%d",&n,&m,&d);ans=calc(n/d,m/d);printf("%d\n",ans);}return 0; }

GCD HDU - 1695
Visible Lattice Points SPOJ - VLATTICE
P1829 [國家集訓(xùn)隊]Crash的數(shù)字表格 / JZPTAB
P3911 最小公倍數(shù)之和
P2522 [HAOI2011]Problem b
P3327 [SDOI2015]約數(shù)個數(shù)和
P3455 [POI2007]ZAP-Queries
P2257 YY的GCD

總結(jié)

以上是生活随笔為你收集整理的莫比乌斯反演+例题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。