Description：

定义 $f(n)$ 为 $n$ 所含质因子的最大幂指数。求： $$ \sum_{i=1}^n\sum_{j=1}^mf(\gcd(i,j)) $$ $T\leqslant 10^4,1\leqslant n,m\leqslant10^7$

Solution：

数据范围显然除法分块。

反演得： $$ \sum_{T=1}^{\min(n,m)}\lfloor\frac a T\rfloor\lfloor\frac b T\rfloor\sum_{d|T}f(d)\mu(\frac T d) $$ 为了除法分块我们可以设： $$ val(T)=\sum_{d|T}f(d)\mu(\frac T d) $$ 那么如果我们可以快速计算 $val(T)$ 的值就可以除法分块了，由于这个奇怪的定义肯定是要分析这个函数的性质。

首先如果 $T$ 中存在两个质数的指数不同，那么答案一定是 $0$ ，因为 $f(d)$ 的取值只与指数最大的那些有关，而无论对于这些数的哪种情况，其他数字的取值都是奇偶对应的，那么由于 $\mu$ 最后一定会消光。如果所有指数都相同，设为 $k$ ，那么首先 $d$ 中所有数的指数都为 $k$ 或 $k-1$ ，否则 $\mu(\frac T d)=0$ ，那么我们枚举第一个指数为 $k$ 的位置，对于所有不是最后一个的位置，他之后的选择也是奇偶对应的，可以用 $\mu$ 消掉，还剩全为 $k-1$ 的方案数和只有最后一个为 $k$ 的方案数，他们的值一定是 $(a-1)\times(-1)^k+a\times(-1)^{k-1}=(-1)^{k+1}$ 。然后用奇怪的做法线性筛出 $f(d)$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 10000010

bool isprime[MAXN];

int prime[MAXN],tot = 0,pows[MAXN],cnt[MAXN];

int val[MAXN],sum[MAXN];

void init()

{

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

	val[1] = 0;

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

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			pows[i] = i;

			cnt[i] = 1;val[i] = 1;

		}

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

		{

			int k = i * prime[j];

			isprime[k] = false;

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

			{

				pows[k] = pows[i] * prime[j];

				cnt[k] = cnt[i] + 1;

			}

			else

			{

				pows[k] = prime[j];

				cnt[k] = 1;

			}

			if(k / pows[k] == 1)val[k] = 1;

			else if(cnt[k] == cnt[k / pows[k]])val[k] = -val[k / pows[k]];

			else val[k] = 0;

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

		}

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

	}

	return;

}

typedef long long ll;

void work()

{

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

	ll ans = 0;

	for(ll l = 1,r;l <= min(n,m);l = r + 1)

	{

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

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

	}

	cout << ans << endl;

	return;

}

int main()

{

	init();

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}