洛谷 P1447

P1447 [NOI2010]能量采集

題目連結:P1447 [NOI2010]能量采集

題目大意

求 \(\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}gcd(i, j) \times 2 - 1\)

solution

如果有錯誤,歡迎指出,如不會莫比烏斯反演和狄利克雷卷積,請自行百度

\(\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}gcd(i, j) \times 2 - 1 \Rightarrow \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}gcd(i, j) \times 2 - nm\)

那我們隻需要處理 \(\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}gcd(i, j)\) 即可,那我們怎麼辦呢?

莫比烏斯反演,這就是莫比烏斯反演的闆子題

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

\(\Rightarrow f(k) = \sum\limits_{i = 1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j = 1}^{\left\lfloor\frac{m}{k}\right\rfloor}[\gcd(i,j) == 1]\)

\(\Rightarrow f(k) = \sum\limits_{i = 1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j = 1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum\limits_{d|\gcd(i,j)}\mu(d)\)

\(\Rightarrow f(d) = \sum\limits_{i = 1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{j = 1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum\limits_{d|i}\sum\limits_{d|j}\mu(d)\)

\(\Rightarrow f(k) = \sum\limits_{d = 1}^{\left\lfloor\frac{min(n, m)}{k}\right\rfloor}\mu(d)\sum\limits_{i = 1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum\limits_{d|i}\sum\limits_{j = 1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum\limits_{d|j}1\)

\(\Rightarrow f(k) = \sum\limits_{d = 1}^{\left\lfloor\frac{min(n, m)}{k}\right\rfloor}\mu(d)\left\lfloor\frac{n}{kd}\right\rfloor\left\lfloor\frac{m}{kd}\right\rfloor\)

然後我們用一下整數分塊,求出每一個 \(f(k) \times k\) 加起來就是 \(\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}gcd(i, j)\)

然後我們逾時了, 那我們怎麼辦呢?

狄利克雷卷積,能幫我們完美的解決這個問題

我們繼續操作我們推出的式子

\(\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}gcd(i, j) = \sum\limits_{k = 1}^{min(n, m)}f(k) \times k\)

\(\Rightarrow \sum\limits_{k = 1}^{min(n, m)}k \sum\limits_{d = 1}^{\left\lfloor\frac{min(n, m)}{k}\right\rfloor}\mu(d)\left\lfloor\frac{n}{kd}\right\rfloor\left\lfloor\frac{m}{kd}\right\rfloor\)

\(\Rightarrow \sum\limits_{k = 1}^{min(n, m)}k \sum\limits_{dk = 1}^{min(n, m)}\mu(d)\left\lfloor\frac{n}{kd}\right\rfloor\left\lfloor\frac{m}{kd}\right\rfloor\)

令 \(T=dk\)

\(\Rightarrow \sum\limits_{k = 1}^{min(n, m)}k \sum\limits_{T = 1}^{min(n, m)}[k|T]\mu(\frac{T}{k})\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\)

\(\Rightarrow \sum\limits_{k = 1}^{min(n, m)}\sum\limits_{k|T}^{min(n, m)}k\mu(\frac{T}{k})\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\)

\(\Rightarrow \sum\limits_{T = 1}^{min(n, m)}\sum\limits_{k|T}^{min(n, m)}k\mu(\frac{T}{k})\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\)

\(\Rightarrow \sum\limits_{T = 1}^{min(n, m)}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\sum\limits_{k|T}^{min(n, m)}k\mu(\frac{T}{k})\)

這時候就要用上我們的狄利克雷卷積了

設 \(h(T) = \sum\limits_{d|T} d\times \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\)

那麼我們帶入原式

\(\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}gcd(i, j) = \sum\limits_{T = 1}^{min(n, m)} \left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor \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);
}
           

時間會刺破青春表面的彩飾，會在美人的額上掘深溝淺槽；會吃掉稀世之珍！天生麗質，什麼都逃不過他那橫掃的鐮刀。

部落客寫的那麼好，就不打賞一下麼（打賞在右邊）