「bzoj2694」LCM - 莫比乌斯反演+线性筛

题目大意

    定义整数$A,B$，求所有满足如下条件的$lcm(a,b)$的和：

$$1\le a\le A,1\le b\le B,\forall n\gt1,n^2\nmid\gcd(a,b)$$

    输出答案模$2^{30}$。

---

题目分析

类似这道题。

$$\begin{aligned} ans&=\sum_d\mu^2(d)\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{d}[\gcd(i,j)=d] \\ &=\sum_d\mu^2(d)d\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}ij\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}ij \\ &=\sum_d\mu^2(d)d\sum_k\mu(k)\sum_{i=1}^{\lfloor\frac n{kd}\rfloor}\sum_{j=1}^{\lfloor\frac m{kd}\rfloor}ijk^2 \end{aligned}$$

令$g(x)=\frac {x(x+1)}2$，则：

$$\begin{aligned} ans&=\sum_d\mu^2(d)d\sum_k\mu(k)k^2f(\lfloor\frac n{kd}\rfloor)g(\lfloor\frac m{kd}\rfloor) \\ &=\sum_Tg(\lfloor\frac nT\rfloor)g(\lfloor\frac mT\rfloor)\sum_{d\mid T}\mu^2(d)\mu(\frac Td)d(\frac Td)^2 \end{aligned}$$

令$f(x)=\sum_{i\mid x}\mu^2(i)\mu(\frac xi)\frac{x^2}i$。
不难发现

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

$f$又是一个积性函数，故还是可以线性筛。

---

代码

#include<bits/stdc++.h>

using namespace std;

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],g[maxn];
bool vst[maxn];

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

int f(int x) {return x*(x+1)/2;}

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