「2014NOI模拟8」老逗的gcd - 莫比乌斯反演+线性筛

题目大意

    对于给定的$n,m$，求$\sum_{i=1}^n\sum_{j=1}^mf(i,j)$。
    其中，函数$f(x,y)$的定义为：

$$f(x,y)=\begin{cases}0 & \exists k\gt1,k^2\mid\gcd(x,y) \\ \gcd(x,y) & \forall k\gt1,k^2\nmid\gcd(x,y)\end{cases}$$

---

题目分析

墙角膜liuguangzhe大佬。

根据莫比乌斯函数的性质有：

$$\begin{aligned} ans&=\sum_{d}\mu^2(d)d\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d] \\ &=\sum_d\mu^2(d)d\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}\sum_{k\mid i,k\mid j}\mu(k) \\ &=\sum_d\mu^2(d)d\sum_k\mu(k)\sum_{k\mid i}^{\lfloor\frac nd\rfloor}\sum_{k\mid j}^{\lfloor\frac md\rfloor} \\ &=\sum_d\mu^2(d)d\sum_k\mu(k)\lfloor\frac n{kd}\rfloor\lfloor\frac m{kd}\rfloor \\ &=\sum_T\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor\sum_{d\mid T}\mu^2(d)\mu(\frac Td)d \end{aligned}$$

令$f(x)=\sum_{i\mid x}\mu^2(i)\mu(\frac xi)i$，则原式为：

$$\sum_T\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor f(T)$$

若$f$函数可以很快求出，则原式可以用分块加速在$O(\sqrt n)$的时间内求出。
考虑$f$函数，若$p$是一个质数，则：

$$f(p)=p-1,f(p^2)=-p,f(p^k)=0(k\gt2)$$

而$f$函数是积性函数卷积、乘积起来，故也是一个积性函数，因此可以线性筛。

---

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=10000005;

int n,m,cnt=0,p[maxn];
bool vst[maxn];
LL f[maxn];

void Sieve(int n) {
	f[1]=1;
	for(int i=2; i<=n; i++) {
		if(!vst[i]) {p[++cnt]=i;f[i]=i-1;}
		for(int j=1; j<=cnt&&i*p[j]<=n; j++) {
			vst[i*p[j]]=1;
			if(i%p[j]==0) {
				f[i*p[j]]=i%(p[j]*p[j])==0?0:-f[i]/(p[j]-1)*p[j];
				break;
			}
			f[i*p[j]]=f[i]*f[p[j]];
		}
	}
	for(int i=2; i<=n; i++)f[i]+=f[i-1];
}

int main() {
	Sieve(10000000);
	int t=Get_Int();
	while(t--) {
		n=Get_Int();
		m=Get_Int();
		LL ans=0;
		for(int i=1,next=0; i<=min(n,m); i=next+1) {
			next=min(n/(n/i),m/(m/i));
			ans+=(f[next]-f[i-1])*(n/i)*(m/i);
		}
		printf("%lld\n",ans);
	}
	return 0;
}