题目大意

求 \(\sum\limits_{p \in primes}\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}[\gcd(x,y)=p]\)。

\(T\) 组数据。

其中 \(1 \leq T \leq 10,1 \leq n,m \leq 10^7\)。

解题思路

设 \(f(n)\) 为满足 \(\gcd(x,y)=d\) 且 \(1 \leq x \leq n\) 和 \(1 \leq y \leq m\) 的 \((x,y)\) 的对数。

\(F(d)\) 为满足 \(d|\gcd(x,y)\) 且 \(1 \leq x \leq n,1 \leq y \leq m\) 的 \((x,y)\) 的对数。

显然，\(F(x)=\frac{n}{x} \times \frac{m}{x}\)，反演后可得：

\[f(x)=\sum\limits_{x|d} \mu(\frac{d}{x})F(d)=\sum\limits_{x|d}\mu(\frac{d}{x})\frac{n}{d} \times \frac{m}{d} \]

那么有：

\[ans=\sum\limits_{p \in primes}^{\min(n,m)}(\sum\limits_{d}^{\min(n,m)}\mu(d)\frac{n}{pd} \times \frac{m}{pd}) \]

但上面那么式子复杂度太高了，考虑化简，设 \(T=pd\)，有：

\[ans=\sum\limits_{i=1}^{\min(n,m)}\frac{n}{T} \times \frac{m}{T}(\sum\limits_{p|T}\mu(\frac{T}{p})) \]

我们可以先预处理出所有 \(T\) 对应的 \(\sum\limits_{p|T}\mu(\frac{T}{p})\) 的值，那么本题就解决了。

时间复杂度为 \(\mathcal O()\)。

CODE

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int _ = 1e7;

int T, n, m;

bool vis[_ + 7];

int tot, pri[_ + 7], g[_ + 7], sum[_ + 7], mu[_ + 7];

void init()
{
	mu[1] = 1;
	for(int i = 2; i < _; ++i)
	{
		if(!vis[i])
		{
			pri[++tot] = i;
			mu[i] = -1;
			g[i] = 1;
		}
		for(int j = 1; j <= tot, i * pri[j] < _; ++j)
		{
			vis[i * pri[j]] = 1;
			if(i % pri[j])
			{
				mu[i * pri[j]] = -mu[i];
				g[i * pri[j]] = mu[i] - g[i];
			}
			else
			{
				mu[i * pri[j]] = 0;
				g[i * pri[j]] = mu[i];
				break;
			}
		}
		sum[i] = sum[i - 1] + g[i];
	}
}

signed main()
{
	init();
	scanf("%lld", &T);
	while(T--)
	{
		scanf("%lld%lld", &n, &m);
		if(n > m) swap(n, m);
		int ans = 0ll;
		for(int i = 1, last; i <= n; i = last + 1)
		{
			last = min(n / (n / i), m / (m / i));
			ans += (n / i) * (m / i) * (sum[last] - sum[i - 1]);
		}
		printf("%lld\n", ans);
	}
	return 0;
}