Rockdu's Blog

5
2 2
4 6
3 4
5 1
23333 33333

7
148
48
15
451085813​

 这道题网上很多题解是化出了一个函数然后快速求这个函数。这里介绍一种简单的容斥方法：考虑用总的减去不合法的，总的是一个子问题：二维LCM求和，这个题就是BZOJ2154。不合法的怎么求呢？我们发现不合法的就是含有平方因子的。然后我们考虑把他们减去：先减去含有2*2因子的，减去3*3因子的，这时含有6*6因子的就被减去了2遍，要加一遍回来……我们发现这就是平方因子开根的莫比乌斯函数。于是就可以算了。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int maxn = 4e6 + 5;
const int mod = 1 << 30;
int pri[maxn], vis[maxn], mu[maxn], n, m;
int S[maxn], mukk[maxn], Smk[maxn];

int GetP(int n) {
	vis[1] = 1, mu[1] = 1, mukk[1] = 1;
	for(register int i = 2; i <= n; ++i) {
		if(!vis[i]) pri[++(*pri)] = i, mu[i] = -1, mukk[i] = 1 - i;
		for(register int j = 1; j <= *pri && pri[j] * i <= n; ++j) {
			vis[i * pri[j]] = 1;
			mu[i * pri[j]] = -mu[i];
			mukk[i * pri[j]] = mukk[i] * mukk[pri[j]];
			if(i % pri[j] == 0) {
				mu[i * pri[j]] = 0;
				mukk[i * pri[j]] = mukk[i];
				break;
			}
		}
	}
	for(register int i = 1; i <= n; ++i)
		S[i] = S[i - 1] + mu[i] * i * i, Smk[i] = mukk[i] * i + Smk[i - 1];
}

inline int Sum(int n) {return n * (n + 1) / 2;}

inline int SigLCM(const int &A, const int &B) {
	register int l = 1, r = 1;
	int mn = min(A, B);
	int ans = 0;
	for(; l <= mn; l = r + 1) {
		r = min(A / (A / l), B / (B / l));
		ans += Sum(A / l) * Sum(B / l) * (Smk[r] - Smk[l - 1]);
	}
	return ans;
}

int GetAns(const int &A, const int &B) {
	register int l = 1, r = 1;
	int ans = 0, mn = min(A, B), lsq = 1;
	for(; lsq <= mn; l = r + 1, lsq = l * l) {
		r = (int)sqrt(min(A / (A / (lsq)), B / (B / (lsq))));
		ans += (S[r] - S[l - 1]) * SigLCM(A / (lsq), B / (lsq));
	}
	return (ans + mod) % mod;
}

int t;
int main() {
	GetP(4e6);
	scanf("%d", &t);
	while(t--) {
		scanf("%d%d", &n, &m);
		printf("%d\n", (GetAns(n, m) + mod) % mod);
	}
	return 0;
}