夏晓光(loveJY)的博客

qwq啊

zhqwq早切掉的一道题

首先把式子写出来

$\sum_{i=1}^n\sum_{j=1}^md(i*j)$

我们有经典结论

$d(i*j)=\sum_{p|i}\sum_{q|j}[gcd(p,q)==1]$

证明在zhqwq的博客里面有qwq

这里我们给出较为简洁的一个:

对于n,m的每个质因数p,设$n=n'*p^a,m=m'*p^b$

我们可知在nm中p的贡献是$(a+b+1)$

然后观察这个形式,我们会发现这样的数对会被统计

$(i'*p^(a),j'),(i'*p^(a-1),j').....(i',j')......(i',j'*p)........(i',j'*p^(b))$

共a+b+1个,故上述式子成立

然后我们可以做出一个决策qwq

$\sum_{i=1}^n\sum_{j=1}^m\sum_{p|i}\sum_{q|j}[gcd(p,q)==1]$

$\sum_{i=1}^n\sum_{j=1}^m\sum_d^{min(i,j)}\mu(d)\frac{i}{d}\frac{j}{d}$

然后您就把d再提到最前面,然后i,j从d开始枚举,反正就错了

正确的解决方法是:直接把d提到最最最前面

$\sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^{n/d}\lfloor\frac{n}{id}\rfloor\sum_{j=1}^{m/d}\lfloor\frac{m}{jd}\rfloor$

这东西就可以整除分块根号求了!

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 5e4 + 7;
int n, m, T;
int mu[MAXN], isp[MAXN], pri[MAXN];
int f[MAXN];
ll g[MAXN];
inline void init() {
	int tot = 0;
	mu[1] = 1;
	for(int i = 2; i < MAXN; ++i) {
		if(!isp[i]) {
			isp[i] = 1;
			pri[++tot] = i;
			mu[i] = -1;
		}
		for(int j = 1; j <= tot && i * pri[j] < MAXN; ++j) {
			isp[i * pri[j]] = 1;
			if(i % pri[j] == 0) {
				mu[i * pri[j]] = 0;
				break;
			} else mu[i * pri[j]] = -mu[i];
		}
	}
	for(int i = 1; i < MAXN; ++i) {
		f[i] = f[i - 1] + mu[i];
		// printf("%d %d\n", i, mu[i]);
	}
	for(int n = 1; n < MAXN; ++n) {
		int l = 1, r = 1;
		for(; l <= n; l = r + 1) {
			// printf("%d %d\n", l, r);
			r = n / (n / l);
			g[n] = g[n] + (r - l + 1) * (n / l);
		}
	}
}

inline void solve() {
	int l = 1, r = 1;
	ll ans = 0;
	if(n > m)n ^= m ^= n ^= m;
	for(; l <= n; l = r + 1) {
		r = min(n / (n / l), m / (m / l));
		// printf("%d %d %d %d %lld %lld %d\n", l, r, n / l, r - l + 1, g[n / l], g[m / l], f[r] - f[l - 1]);
		ans = ans + 1ll * (f[r] - f[l - 1]) * (g[n / l]) * (g[m / l]);
	}
	printf("%lld\n", ans);
}

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