首页 > 代码库 > 莫比乌斯反演笔记
莫比乌斯反演笔记
已知：$\sum_{t|n}\mu (t)=[n=1]$
一,求${\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]}$
其中$n\leq 1e7,m\leq 1e7$
原式${=\sum_{i=1}^{n}\sum_{j=1}^{m} \sum_{t|i,t|j}\mu (t)}$
${=\sum_{t=1}^{n}\left \lfloor \frac{n}{t} \right \rfloor\left \lfloor \frac{m}{t} \right \rfloor\mu (t)}$
线性筛莫比乌斯函数即可
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1001010 #define llg long long11 #define N 2010 12 #define yyj() freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);13 llg n,m,T,cnt,prime[maxn],mobius[maxn],bj[maxn];14 15 void init_mobius()16 {17 mobius[1]=1;18 for (llg i=2;i<=N;i++)19 {20 if (!bj[i])21 {22 prime[++cnt]=i; mobius[i]=-1;23 }24 for (llg j=1;j<=cnt && prime[j]*i<=N;j++)25 {26 bj[i*prime[j]]=1;27 if (i%prime[j]) mobius[i*prime[j]]=-mobius[i];28 else29 {30 mobius[i*prime[j]]=0;31 break;32 }33 }34 }35 }36 37 int main()38 {39 yyj();40 cin>>T;41 init_mobius();42 // for (llg i=1;i<=10;i++) cout<<i<<"-->"<<mobius[i]<<endl;43 T=10;44 while (T--)45 {46 llg ans=0;47 scanf("%lld%lld",&n,&m);48 for (llg t=1;t<=n;t++) 49 {50 ans+=floor((n/t))*floor((m/t))*mobius[t];51 }52 printf("%lld\n",ans*4+4);53 }54 return 0;55 }
二,求${\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=g]$,$n\leq 1e7,m\leq 1e7}$
令：n\leq m
原式${=\sum _{g=1}^{n}g\sum _{i=1}^{\frac{n}{g}}\sum _{j=1}^{\frac{m}{g}}[gcd(i,j)=1]}$
${=\sum _{g=1}^{n}g\sum _{i=1}^{\left \lfloor \frac{n}{g} \right \rfloor}\sum _{j=1}^{\left \lfloor \frac{m}{g} \right \rfloor}\sum _{t|i,t|j}\mu (t)}$
${=\sum _{g=1}^{n}g\sum_{t=1}^{t\leq \frac{n}{g}}\left \lfloor \frac{n}{tg} \right \rfloor\left \lfloor \frac{m}{tg} \right \rfloor\mu (t)}$
推到这一步可以发现${\sum _{g=1}^{n}\sum_{t=1}^{t\leq \frac{n}{g}}}$是一个调和级数，预处理莫比乌斯函数，然后直接枚举g,然后就可以了。
莫比乌斯反演笔记