洛谷 P1447

题目链接:P1447 [NOI2010]能量采集

题目大意

求 (sumlimits_{i = 1}^{n}sumlimits_{j = 1}^{m}gcd(i, j) imes 2 - 1)

solution

如果有错误,欢迎指出,如不会莫比乌斯反演和狄利克雷卷积,请自行百度

(sumlimits_{i = 1}^{n}sumlimits_{j = 1}^{m}gcd(i, j) imes 2 - 1 Rightarrow sumlimits_{i = 1}^{n}sumlimits_{j = 1}^{m}gcd(i, j) imes 2 - nm)

那我们只需要处理 (sumlimits_{i = 1}^{n}sumlimits_{j = 1}^{m}gcd(i, j)) 即可,那我们怎么办呢?

莫比乌斯反演,这就是莫比乌斯反演的板子题

(f(d) = sumlimits_{i = 1}^{n}sumlimits_{j = 1}^{m}[gcd(i,j) == k])

(Rightarrow f(k) = sumlimits_{i = 1}^{leftlfloorfrac{n}{k} ight floor}sumlimits_{j = 1}^{leftlfloorfrac{m}{k} ight floor}[gcd(i,j) == 1])

(Rightarrow f(k) = sumlimits_{i = 1}^{leftlfloorfrac{n}{k} ight floor}sumlimits_{j = 1}^{leftlfloorfrac{m}{k} ight floor}sumlimits_{d|gcd(i,j)}mu(d))

(Rightarrow f(d) = sumlimits_{i = 1}^{leftlfloorfrac{n}{k} ight floor}sumlimits_{j = 1}^{leftlfloorfrac{m}{k} ight floor}sumlimits_{d|i}sumlimits_{d|j}mu(d))

(Rightarrow f(k) = sumlimits_{d = 1}^{leftlfloorfrac{min(n, m)}{k} ight floor}mu(d)sumlimits_{i = 1}^{leftlfloorfrac{n}{k} ight floor}sumlimits_{d|i}sumlimits_{j = 1}^{leftlfloorfrac{m}{k} ight floor}sumlimits_{d|j}1)

(Rightarrow f(k) = sumlimits_{d = 1}^{leftlfloorfrac{min(n, m)}{k} ight floor}mu(d)leftlfloorfrac{n}{kd} ight floorleftlfloorfrac{m}{kd} ight floor)

然后我们用一下整数分块,求出每一个 (f(k) imes k) 加起来就是 (sumlimits_{i = 1}^{n}sumlimits_{j = 1}^{m}gcd(i, j))

然后我们超时了, 那我们怎么办呢?

狄利克雷卷积,能帮我们完美的解决这个问题

我们继续操作我们推出的式子

(sumlimits_{i = 1}^{n}sumlimits_{j = 1}^{m}gcd(i, j) = sumlimits_{k = 1}^{min(n, m)}f(k) imes k)

(Rightarrow sumlimits_{k = 1}^{min(n, m)}k sumlimits_{d = 1}^{leftlfloorfrac{min(n, m)}{k} ight floor}mu(d)leftlfloorfrac{n}{kd} ight floorleftlfloorfrac{m}{kd} ight floor)

(Rightarrow sumlimits_{k = 1}^{min(n, m)}k sumlimits_{dk = 1}^{min(n, m)}mu(d)leftlfloorfrac{n}{kd} ight floorleftlfloorfrac{m}{kd} ight floor)

令 (T=dk)

(Rightarrow sumlimits_{k = 1}^{min(n, m)}k sumlimits_{T = 1}^{min(n, m)}[k|T]mu(frac{T}{k})leftlfloorfrac{n}{T} ight floorleftlfloorfrac{m}{T} ight floor)

(Rightarrow sumlimits_{k = 1}^{min(n, m)}sumlimits_{k|T}^{min(n, m)}kmu(frac{T}{k})leftlfloorfrac{n}{T} ight floorleftlfloorfrac{m}{T} ight floor)

(Rightarrow sumlimits_{T = 1}^{min(n, m)}sumlimits_{k|T}^{min(n, m)}kmu(frac{T}{k})leftlfloorfrac{n}{T} ight floorleftlfloorfrac{m}{T} ight floor)

(Rightarrow sumlimits_{T = 1}^{min(n, m)}leftlfloorfrac{n}{T} ight floorleftlfloorfrac{m}{T} ight floorsumlimits_{k|T}^{min(n, m)}kmu(frac{T}{k}))

这时候就要用上我们的狄利克雷卷积了

设 (h(T) = sumlimits_{d|T} d imes mu(frac{T}{d}))

(Rightarrow h = id * mu)

(Rightarrow h * 1 = id * (mu * 1))

(mu * 1 = epsilon)

(Rightarrow h * 1 = id * epsilon)

(Rightarrow h * 1 = id)

(phi * 1 = id)

(Rightarrow h = phi)

那么我们带入原式

(sumlimits_{i = 1}^{n}sumlimits_{j = 1}^{m}gcd(i, j) = sumlimits_{T = 1}^{min(n, m)} leftlfloorfrac{n}{T} ight floorleftlfloorfrac{m}{T} ight floor phi(T))

然后我们有线性筛筛欧拉函数就好了, (O(min(n, m)))

Code:

/**
*    Author: Alieme
*    Data: 2020.9.7
*    Problem: Luogu P1447
*    Time: O(min(n, m))
*/
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>

#define int long long
#define rr register

#define inf 1e9
#define MAXN 100010

using namespace std;

inline int read() {
	int s = 0, f = 0;
	char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

void print(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + 48);
}

int n, m, ans, tot;

int phi[MAXN], sum[MAXN], prime[MAXN];

bool vis[MAXN];

inline void init() {
	phi[1] = 1;
	for (rr int i = 2; i <= 100000; i++) {
		if (!vis[i]) prime[++tot] = i, phi[i] = i - 1;
		for (rr int j = 1; j <= tot; j++) {
			if (i * prime[j] > 100000) break;
			vis[i * prime[j]] = 1;
			phi[i * prime[j]] = phi[i] * phi[prime[j]];
			if ((i % prime[j]) == 0) {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
		}
	}
	for (rr int i = 1; i <= 100000; i++) sum[i] = sum[i - 1] + phi[i];
}

signed main() {
	n = read();
	m = read();
	init();
	for (rr int l = 1, r; l <= min(n, m); l = r + 1) {
		r = min(n / (n / l), m / (m / l));
		ans += (sum[r] - sum[l - 1]) * (n / l) * (m / l);
	}
	ans = 2 * ans - n * m;
	print(ans);
}