HDU6175(莫比乌斯反演)

思路

$$\begin{aligned} Ans&=\sum_{i=1}^n\sum_{j=1}^m\mu(lcm(i,j))\\ &=\sum_{i=1}^n\sum_{j=1}^m\mu(\frac{ij}{gcd(i,j)})\\ &=\sum_{i=1}^n\sum_{j=1}^m\mu(\frac{ij}{k})[gcd(i,j)==k]\\ 乘上\mu(d^2)\\ &=\sum_{i=1}^n\sum_{j=1}^m\mu(i)\mu(j)\mu(k)[gcd(i,j)==k]\\ 枚举k\\ &=\sum_k^n\mu(k)\sum_{i=1}^n\sum_{j=1}^m\mu(i)\mu(j)[gcd(i,j)==k]\\ &=\sum_k^n\mu(k)\sum_{i=1}^\frac{k}{n}\sum_{j=1}^\frac{k}{m}\mu(ik)\mu(jk)[gcd(i,j)==1]\\ 反演\\ &=\sum_k^n\mu(k)\sum_{i=1}^\frac{n}{k}\sum_{j=1}^\frac{m}{k}\mu(ik)\mu(jk)\sum_{d|gcd(i,j)}\mu(d)\\ 把d提取出来，即先枚举d\\ &=\sum_k^n\mu(k)\sum_{d=1}^{\frac{n}{k}}\mu(d)\sum_{i=1}^\frac{n}{kd}\sum_{j=1}^\frac{m}{kd}\mu(ikd)\mu(jkd)\\ 令T=kd\\ &=\sum_{T=1}^n(\sum_{i=1}^{\frac{n}{T}}\mu(iT))(\sum_{j=1}^{\frac{m}{T}}\mu(jT))(\sum_{k|d}\mu(k)\mu(\frac{T}{k}))) \end{aligned}$$

得到上面三部分后，可以预处理出来，时间复杂度O(nlogn),因为要筛。

代码示例

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N = 1e6+10;
int prime[N],cnt,mu[N];
int s3[N],s2[N],s1[N],n,m;
bool vis[N];
void init(){
	mu[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i])prime[cnt++]=i,mu[i]=-1;
		for(int j=0;j<cnt&&i*prime[j]<N;j++){
			vis[i*prime[j]]=true;
			if(i%prime[j]==0){
				mu[i*prime[j]]=0;
				break;
			}
			mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<N;i++)
		for(int j=i;j<N;j+=i)
		s3[j]+=mu[i]*mu[j/i];
}
int main(){
	int t;
	init();
	scanf("%d",&t);
	while(t--){
		scanf("%d %d",&n,&m);
		for(int i=1;i<=max(n,m);i++)s1[i]=s2[i]=0;
		if(n>m)swap(n,m);
		for(int i=1;i<=n;i++){
			for(int j=i;j<=n;j+=i){
				s1[i]+=mu[j];
			}
		}
		for(int i=1;i<=m;i++){
			for(int j=i;j<=m;j+=i){
				s2[i]+=mu[j];
			}
		}
		ll ans = 0;
		for(int i=1;i<=n;i++){
			ans+=s1[i]*s2[i]*s3[i];
		}
		printf("%lld\n",ans);
	}
}