Luogu1891 疯狂 LCM

tony102

2020 年 11 月 14 日

1131 次浏览

暂无评论

1154字数

题解

[Link](https://www.luogu.com.cn/problem/P1891)

## Sol

主要考察的是 $gcd$ 和 $lcm$ 关系的一个性质: $lcm(a, b) = \frac{a \times b}{gcd(a,b)}$

那么我们用这个式子来替换现在的式子

$$\sum_{i=1}^{n} \frac{i \times n}{gcd(i,n)}$$

把乘的 $n$ 这个常数项直接提到外面来,稍微改改

$$n \times \sum_{i=1}^{n} \frac{i}{gcd(i,n)}$$

**常见套路:有整除,gcd,约数的时候,把枚举的东西改成枚举约数,再改成枚举倍数**

那么我们先枚举约数试试

$$n \times \sum_{d|n} \sum_{i=1}^{n} \frac{i}{d} [gcd(i,n) = d]$$

再把中括号(布尔表达式)内的东西同时除一个 $d$

$$n \times \sum_{d|n} \sum_{i=1}^{n} \frac{i}{d} [gcd(\frac{i}{d}, \frac{n}{d}) = 1]$$

再写成枚举倍数的

$$n \times \sum_{d|n} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} i [gcd(i,\frac{n}{d}) = 1]$$

注意到因为 $d|n$,所以 $\frac{n}{d}$ 与 $d$ 等价,全部改成枚举到 $d$

$$n \times \sum_{d|n} \sum_{i=1}^{d} i [gcd(i,d) = 1]$$

现在应该很显然, $[gcd(i,d)=1]$ 就是 $\varphi(d)$

实际上因为 $n$ 的约数是成对出现的,那么一共会有 $\frac{d}{2}$ 对约数,直接把后面的东西利用这个性质算出来.

所以现在就是

$$n \times \sum_{d|n} \frac{\varphi(d)}{2} \times d $$

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 1e6 + 5;

int T, n, tot;
int prime[SIZE], phi[SIZE], isPrime[SIZE], ans[SIZE];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

inline void euler()
{
	int siz = 1e6 + 1;
	phi[1] = isPrime[1] = 1;
	for (register int i = 2; i <= siz; ++ i) {
		if (!isPrime[i]) {
			prime[++ tot] = i, phi[i] = i - 1;
		}
		for (register int j = 1; j <= tot && i * prime[j] <= siz; ++ j) {
			isPrime[i * prime[j]] = 1;
			if (i % prime[j])  phi[i * prime[j]] = phi[i] * phi[prime[j]];
			else {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
		}
	}
}

signed main()
{
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	T = read();
	euler(); int siz = 1e6 + 1;
	for (int i = 1; i <= siz; ++ i) {
		for(int j = 1; i * j <= siz; ++ j) 
			ans[i * j] += (i == 1 ? 1 : 1ll * phi[i] * i / 2);
	}
	while (T --) {
		n = read();
		printf("%lld\n", ans[n] * n * 1ll);
		// puts("");
	}
	return 0;
}
```

最后修改：2021 年 08 月 20 日