P2257 YY的GCD (莫比乌斯反演)

题意:求$$sum_{i=1}^{n}sum_{j=1}{m}[gcd(i,j) = prim]$$
题解:那就开始化式子吧!!

[f(d) = sum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j) = d] ]

[F(x) = sum_{d|x} f(d) = left lfloor frac{n}{x} ight floor left lfloor frac{m}{x} ight floor ]

[f(d) = sum_{d|x} muleft ( frac{x}{d} ight )F(x) ]

[ans= sum_{p in prim}f(p)=sum_{p in prim}sum_{p|x} muleft ( frac{x}{p} ight )left lfloor frac{n}{x} ight floor left lfloor frac{m}{x} ight floor ]

[ans = sum_{pin prim}sum_{t = 1}^{min(left lfloor frac{n}{p} ight floor,left lfloor frac{m}{p} ight floor)}mu(t)left lfloor frac{n}{pt} ight floorleft lfloor frac{m}{pt} ight floor ]

　　令pt = T

[ans=sum_{T=1}^{min(n, m)}left lfloor frac{n}{T} ight floorleft lfloor frac{m}{T} ight floorsum_{p | T, pin prim}mu(frac{T}{p}) ]

　　后面部分显然可以预处理

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool vis[10000005];
int prim[10000005];
int mu[10000005];
int g[10000005];
ll sum[10000005];
int cnt;

void get_mu(int n)
{
	mu[1] = 1;
	for(int i = 2; i <= n; i++)
	{
		if(!vis[i])
		{
			mu[i] = -1;
			prim[++cnt] = i;
		}
		for(int j = 1; j <= cnt && i * prim[j] <= n; j++)
		{
			vis[i * prim[j]] = 1;
			if(i % prim[j] == 0) break;
			else mu[i * prim[j]] -= mu[i];
		}
	}
	
	for(int i = 1; i <= cnt; i++)
		for(int j = 1; j * prim[i] <= n; j++) g[j * prim[i]] += mu[j];
	for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (ll)g[i];
}

int main()
{
	cnt = 0;
	get_mu(10000000);
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int n, m;
		scanf("%d%d", &n, &m);
		if(n > m) swap(n, m);
		ll ans = 0;
		for(int i = 1, r; i <= n; i = r + 1)
		{
			r = min(n / (n / i), m / (m / i));
			ans += 1LL * (n / i) * (m / i) * (sum[r] - sum[i - 1]);
		}
		printf("%lld
", ans);
	}
	return 0;
}