davidwang's Blog

看了这道题目然后发现省队说过，然后手推了一下。 然后发现各种坑点Wa了好几发比如mod10^8+9什么的

$$ ∑_{i=1}^n∑_{j=1}^mlcm(i,j) $$ 枚举因子

$$ =∑_d∑_{i=1}^{[n/d]}∑_{j=1}^{[m/d]}ijd[gcd(i,j)=1] $$ 反演最后一部分

$$ =∑_dd∑_{i=1}^{[n/d]}∑_{j=1}^{[m/d]}ij∑_{e(e|gcd(i,j))}μ(e) $$ 把e放到前面去枚举，注意因为后面i,j变成了i/j,e/j所以要加上e^2

$$ =∑_dd∑_ee^2μ(e)∑_{i=1}^{[n/ed]}∑_{j=1}^{[m/ed]}ij $$ 提到前面来然后枚举 $$ D=d*e $$ 定义 $$ S(n) = ∑_{i=1}^ni $$

$$ =∑_DS(n/d)S(m/d)∑_{d(d|D)}(D/d)^2*μ(D/d)*d $$

后面这一坨是积性的。然后就可以线性筛了，如果利用约束和的条件可以更简单

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <deque>
#include <queue>
using namespace std;
#define LL long long 
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 10000000,mod=(int)1e8+9;
LL h[N+10],prime[N+10],vis[N+10];
int n,m,cnt,T;
int init()
{
	h[1]=1;
	for (int i=2;i<=N;i++){
		if (!vis[i]){
			prime[++cnt]=i;
			h[i]=(i-(LL)i*i)%mod;
		}
		for (int j=1;j<=cnt && i*prime[j]<=N;j++){
			vis[i*prime[j]]=1;
			if (i%prime[j]){
				h[i*prime[j]]=h[i]*h[prime[j]]%mod;
			}else{
				h[i*prime[j]]=h[i]*prime[j]%mod;
				break;
			}
		}
	}
	for (int i=2;i<=N;i++) h[i]=(h[i]+h[i-1])%mod;
	T=read();
	return 0;
}
inline LL S(LL a){
	return (a*(a+1)/2)%mod;
}
inline void solve(int n,int m){
	LL ans=0;
	if (n>m) swap(n,m);
	int last=0;
	for (int i=1;i<=n;i=last+1){
		last=min(n/(n/i),m/(m/i));
		ans=(ans+(S(n/i)*S(m/i)%mod)*(h[last]-h[i-1]+mod)%mod)%mod;
	}
	while (ans<0) ans+=mod;
	printf("%lld\n",ans);
	return;
}
int main(){
	init();
	while (T--){
		int n=read(),m=read();
		solve(n,m);
	}
	return 0;
}