Description：

求 $\begin{align}\sum_{i=1}^N\sum_{j=1}^Mlcm(i,j)\end{align}$

其中 $gcd(i,j)$ 不含平方因子。

Solution：

不含平方因子很难做，先不管他。

$\begin{align}\sum_{i=1}^N\sum_{j=1}^Mlcm(i,j)\end{align}$

$\begin{align}=\sum_{i=1}^N\sum_{j=1}^M\frac{i\times j}{gcd(i,j)}\end{align}$

外层枚举 $gcd$ 得：

$\begin{align}\sum_d\sum_{i=1}^N\sum_{j=1}^M\frac{i\times j}{d}\times[gcd(i,j)==d]\end{align}$

$\begin{align}=\sum_d\sum_{i=1}^{\lfloor\frac N d\rfloor}\sum_{j=1}^{\lfloor\frac M d\rfloor}i\times j\times d\times[gcd(i,j)==1]\end{align}$

$\begin{align}=\sum_d\sum_{i=1}^{\lfloor\frac N d\rfloor}\sum_{j=1}^{\lfloor\frac M d\rfloor}i\times j\times d\times\sum_{k|i,k|j}\mu(k)\end{align}$

$\begin{align}=\sum_dd\times\sum_k\mu(k)\sum_{i=1,i|k}^{\lfloor\frac N d\rfloor}\sum_{j=1,j|k}^{\lfloor\frac M d\rfloor}i\times j\end{align}$

$\begin{align}=\sum_dd\times\sum_k\mu(k)k^2\sum_{i=1,}^{\lfloor\frac N {dk}\rfloor}i\sum_{j=1}^{\lfloor\frac M {dk}\rfloor}j\end{align}$

设 $T=k\times d$ ，在外面枚举 $T$ ，内层枚举 $d$ ，则 $k=\frac T d$ 。

原式 $\begin{align}=\sum_{T=1}^{min(m,n)}S_{\lfloor\frac n T\rfloor}\times S_{\lfloor\frac m T\rfloor}\sum_{d|T}d\times\mu(\frac T d)\times(\frac T d)^2\end{align}$

设 $g(T)=\begin{align}\sum_{d|T}d\times\mu(\frac T d)\times(\frac T d)^2\end{align}$

$g$ 可以通过枚举因子和倍数求出，根据调和级数可知复杂度为 $O(nlog_2n)$ 。由于 $d$ 不能含平方因子，在枚举 $d$ 时判断 $\mu(d)$ 是否不为 $0$ 即可。

然后就可以除法分块了。

切记要计算 $g$ 前缀和，切记要等到 $g$ 计算完了再计算前缀和，不然样例都过不了。

模 $2^{30}$ 用 $int$ 自然溢出。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int testcases;

#define MAXN 4000010

int prime[MAXN],tot = 0;

bool isprime[MAXN];

int mu[MAXN];

#define MOD (1 << 30)

int g[MAXN],sum[MAXN];

void init()

{

	for(int i = 2;i < MAXN;++i)isprime[i] = true;

	mu[1] = 1;

	for(int i = 2;i < MAXN;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			mu[i] = -1;

		}

		for(int j = 1;j <= tot && i * prime[j] < MAXN;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)

			{

				mu[i * prime[j]] = 0;

				break;

			}

			else

			{

				mu[i * prime[j]] = -1 * mu[i];

			}

		}

	}

	memset(g,0,sizeof(g));

	for(int i = 1;i < MAXN;++i)

	{

		if(mu[i] == 0)continue;

		for(int j = 1;i * j < MAXN;++j)

		{

			g[i * j] += i * mu[j] * j * j;

		}

	}

	for(int i = 1;i < MAXN;++i)

	{

		sum[i] = sum[i - 1] + g[i];

	}

	return;

}

int n,m;

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

int main()

{

	init(); 

	scanf("%d",&testcases);

	for(int i = 1;i <= testcases;++i)

	{

		scanf("%d%d",&n,&m);

		int ans = 0;

		if(n > m)swap(n,m);

		for(int l = 1,r = 0;l <= n;l = r + 1)

		{

			r = min(n / (n / l),m / (m / l));

			ans += (sum[r] - sum[l - 1]) * s(n / l) * s(m / l);

		}

		printf("%d\n",(ans % MOD + MOD) % MOD);

	}

	return 0;

}