Description：

求： $$ \sum_{i=1}^n\sum_{j=1}^m\text{lcm}(i,j) $$ $1\leqslant testcases\leqslant 10^4,1\leqslant n,m\leqslant 10^7$

Solution：

套路 $\text{lcm}$ 展开，套路枚举 $\gcd$ ，套路反演，套路交换求和号，套路 $T=dd'$ 之后可以得到： $$ \sum_{T=1}^nT\sum_{d|T}\mu(\frac T d)\frac T d\sum_{i=1}^{\lfloor\frac n T\rfloor}i\sum_{i=1}^{\lfloor\frac m i\rfloor}i $$ 这时按照套路应该是 $O(n\ln n)$ 预处理一个 $val[T]$ ，但是这样会超时，发现 $val[T]$ 是积性函数，于是可以线性筛，然后就是除法分块了。

但是这个好像不是很好线性筛，因为 $i\%prime[j]=0$ 时不好处理，但是发现， $n$ 新产生的约数一定包含 $d^2$ ，也就是说 $\mu$ 为 $0$ ，所以没区别。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAX 10000010

typedef long long ll;

ll n,m;

bool isprime[MAX];

ll prime[MAX],tot = 0;

#define MOD 100000009

ll sum1(ll k){return (k + 1) * k / 2 % MOD;}

ll val[MAX];

ll s[MAX];

void init()

{

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

	val[1] = 1;

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

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			val[i] = (-i + 1 + MOD) % MOD;

		}

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

		{

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

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

			{

				val[i * prime[j]] = val[i];

				break;

			}

			else

			{

				val[i * prime[j]] = val[i] * val[prime[j]] % MOD;

			}

		}

	}

	for(int i = 1;i < MAX;++i)s[i] = (s[i - 1] + val[i] * i) % MOD;

	return;

}

void work()

{

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

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

	ll ans = 0;

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

	{

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

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

	}

	cout << ans << endl;

	return;

}

int main()

{

	init();

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}