题解 P3455 [POI2007]ZAP-Queries

题目 link

是莫比乌斯函数还是莫比乌斯反演捏？感觉好多所谓“莫比乌斯反演”题只要拿 \(\mu\) 性质给暴力替换一下就能做出来了，比如这题 qwq

答案是这个式子：\(\sum\limits_{i = 1}^{a}\sum\limits_{j = 1}^b [\gcd(i, j) = k]\)，我们默认 \(n\le m\)。

套路操作是除以一个 \(k\)，然后 \(\gcd(i, j)\) 就会变成互质的。所以是 \(\sum\limits_{i = 1}^{\lfloor\frac{a}{k}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{b}{k}\rfloor} [\gcd(i, j) = 1]\)。

然后也是一个很套路的东西，众所周知，\(\sum\limits_{d|n}\mu(d) = [n = 1]\)，所以 \([\gcd(i, j) = 1] = \sum\limits_{d|\gcd(i, j)}\mu(d)\)

然后就会得到 \(\sum\limits_{i = 1}^{\lfloor\frac{a}{k}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{b}{k}\rfloor} \sum\limits_{d|\gcd(i, j)}\mu(d)\)。

根据套路，我们可以把 \(d\) 丢到前面，然后以 \(\mu(d)\) 为系数，得到这个 \(\sum\limits_{d = 1}^{n}\mu(d)\sum\limits_{i = 1}^{\lfloor\frac{a}{k}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{b}{k}\rfloor}[d|\gcd(i, j)]\)。

\([d|\gcd(i, j)]\) 等价于 \(d|i, d|j\)，所以就是 \(\sum\limits_{d = 1}^{n}\mu(d)\sum\limits_{i = 1}^{\lfloor\frac{a}{k}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{b}{k}\rfloor}[d|i, d|j]\)。

到这里就明朗了吧！最后两个 sigma 很容易化掉，所以就有 \(\sum\limits_{d = 1}^{n}\mu(d)\lfloor\dfrac{a}{kd}\rfloor\lfloor\dfrac{b}{kd}\rfloor\)

后面那一坨明显可以整除分块搞掉。

喜闻乐见的代码

//SIXIANG
#include <iostream> 
#define int long long
#define MAXN 500000
#define QWQ cout << "QWQ" << endl;
using namespace std;
bool flag[MAXN + 10];
int mu[MAXN + 10], pri[MAXN + 10], tot = 0, sum[MAXN + 10];
void prepare() {
	mu[1] = 1;
	for(int p = 2; p <= MAXN; p++) {
		if(!flag[p]) {
			mu[p] = -1;
			pri[++tot] = p;
		}
		for(int i = 1; i <= tot && p * pri[i] <= MAXN; i++) {
			flag[p * pri[i]] = 1;
			if(p % pri[i] != 0)
				mu[p * pri[i]] = mu[p] * mu[pri[i]];
			else {
				mu[p * pri[i]] = 0;
				break;
			}
		}
	}
	
	for(int p = 1; p <= MAXN; p++)
		sum[p] = sum[p - 1] + mu[p];
} 

void init() {
	int a, b, k;
	cin >> a >> b >> k;
	if(a > b) swap(a, b);
	int A = a / k, B = b / k;
	
	int l = 1, r = 1, ans = 0;
	for(; l <= A; l = r + 1) {
		r = min((A / (A / l)), ((B / (B / l))));
		ans += ((sum[r] - sum[l - 1]) * (A / l) * (B / l));
	}
	cout << ans << endl;
}

signed main() {
	prepare();
	int T; cin >> T;
	while(T--)
		init();
}