CF1717E 题解

题解—搬运

枚举 $a + b$，则 $c = n - (a + b)$。

$\gcd(a, b)$ 一定是 $a + b$ 的因数，所以接下来枚举 $a + b$ 的每一个因数，计算其作为 $\gcd(a, b)$ 的贡献。

易见，$d | (a + b)$ 作为 $\gcd(a, b)$ 对答案的贡献次数，为满足 $a^\prime \perp b^\prime$ 且 $a^\prime + b^\prime = \frac{a + b}{d}$ 的有序正整数对 $(a^\prime, b^\prime)$ 的数目。

由更相减损术可知 $\gcd(a + b, b) = \gcd(a, b)$，故 $\gcd\left(\frac{a + b}{d}, b^\prime\right) = \gcd(a^\prime + b^\prime, b^\prime) = \gcd(a^\prime, b^\prime) = 1$。由此可知，有序正整数对 $(a^\prime, b^\prime)$ 满足 $a^\prime \perp b^\prime$ 且 $a^\prime + b^\prime = \frac{a + b}{d}$，当且仅当 $\frac{a + b}{d} \perp b^\prime$ 且 $a^\prime + b^\prime = \frac{a + b}{d}$。

从而，这样的正整数对数目，即为小于 $\frac{a + b}{d}$ 且与之互质的正整数数目。易见这就是 $1$ 处取值修改为 $0$ 的欧拉函数在 $\frac{a + b}{d}$ 处的值。

定义

$$\displaylines{f(n) = \begin{cases}0 & (n=1) \\ \varphi(n) & (n \not= 1)\end{cases}}$$

$f$ 可以用筛法预处理出来。

则最终我们有

$$\sum_{a+b+c=n}\operatorname{lcm}(c,\gcd(a,b)) = \sum_{s=2}^{n-1}\sum_{d|s}f\left(\frac{s}{d}\right)\operatorname{lcm}(n-s,d)$$

若用枚举范围内每一个因数的所有倍数的方式预处理出每一个数的所有因数，时间复杂度为 $O(n\log n)$；若直接 $O(\sqrt n)$ 枚举因数，则时间复杂度为 $O(n\sqrt n)$。均可以通过。

代码

#include<bits/stdc++.h>

using namespace std;

namespace acah
{
	constexpr int p = 1e9 + 7;
	
	int n, ans;
	int pr[100007], pc, phi[100007];
	bool vis[100007];
	vector<int> dvs[100007];
	
	inline void sieve()
	{
		for(int i = 2; i <= n; i++) {
			if(!vis[i]) pr[++pc] = i, phi[i] = i - 1;
			for(int j = 1; j <= pc && 1ll * i * pr[j] <= n; j++) {
				vis[i * pr[j]] = true;
				if(i % pr[j]) phi[i * pr[j]] = phi[i] * (pr[j] - 1);
				else {phi[i * pr[j]] = phi[i] * pr[j]; break;}
			}
		}
	}
	
	inline int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
	
	inline long long lcm(int a, int b) {return 1ll * a / gcd(a, b) * b;}
	
	int work()
	{
		scanf("%d", &n), sieve();
		for(int i = 1; i <= n; i++) for(int j = i; j <= n; j += i) dvs[j].emplace_back(i);
		for(int i = 2; i < n; i++) for(int d : dvs[i])
			ans += 1ll * lcm(n - i, d) * phi[i / d] % p, ans -= (ans >= p ? p : 0);
		printf("%d", ans);
		return 0;
	}
}

int main() {return acah::work();}