[bzoj 2693] jzptab

求 , T组数据. (T≤10^4, n,m≤10^7) 同[bzoj 2154] Crash的数字表格,

不同的是, 本题有多组询问, 原先的线性做法需要进一步优化.

但是不知从何入手, 学习了一下题解.

发现式子具有卷积的形式. 记, 则

积性函数的两个性质: - 积性函数的乘积是积性函数. - 积性函数的狄利克雷卷积是积性函数.

由此可知 是积性函数, 可以用线性筛计算. 当 时, , 因为其余项必然有平方因子, 莫比乌斯函数值等于0.

预处理出 的前缀和, 利用商分段的性质计算, 总时间复杂度 .

const int MOD = 1e8 + 9, N = 1e7;
int f[N+1];

void sieve()
{
	static bool v[N+1];
	static int p[N/10], ptr;
	
	f[1] = 1;
	rep (i, 2, N+1) {
		if (!v[i]) {
			p[ptr++] = i;
			f[i] = 1-i;
		}
		for (int j = 0, t; j < ptr && (t = i*p[j]) <= N; ++j) {
			v[t] = true;
			if (i % p[j]) {
				f[t] = 1LL * f[i] * f[p[j]] % MOD;
			} else {
				f[t] = f[i];
				break;
			}
		}
	}
	rep (i, 2, N+1) f[i] = (1LL*f[i]*i + f[i-1]) % MOD;
}

inline int sum(int n, int m)
{
	return (1LL*n*(n+1)/2%MOD) * (1LL*m*(m+1)/2%MOD) % MOD;
}

int solve(int n, int m)
{
	int l = min(n, m), ans = 0;
	for (int i = 1, j; i <= l; i = j+1) {
		int _n = n/i, _m = m/i;
		j = min(n/_n, m/_m);
		ans = (ans + 1LL * sum(_n, _m) * (f[j] - f[i-1] + MOD)) % MOD;
	}
	return (ans + MOD) % MOD;
}

int main()
{
	sieve();
	int T;
	scanf("%d", &T);
	while (T--) {
		int n, m;
		scanf("%d%d", &n, &m);
		printf("%d\n", solve(n, m));
	}
	return 0;
}