CodeForces 1717E【线性筛】
题意：给定 n n n，求所有三元组 ( a , b , c ) (a,b,c) (a,b,c) 满足 a + b + c = n a+b+c=n a+b+c=n 的 lcm ( gcd ( a , b ) , c ) \operatorname{lcm}(\gcd(a,b),c) lcm(gcd(a,b),c) 的和。
思想：
第一层循环枚举 gcd ( a , b ) \gcd(a,b) gcd(a,b) 的值。
然后枚举 a + b a+b a+b 的值。
容易发现， a + b a + b a+b 的值一定是 k × gcd ( a , b ) k\times \gcd (a,b) k×gcd(a,b)， k ∈ N ∗ k\in N^* k∈N∗。
也就是说， ( a , b ) (a,b) (a,b) 的取值方法一共有 φ ( ⌊ n − c gcd ( a , b ) ⌋ ) \varphi(\lfloor\frac{n-c}{\gcd(a,b)}\rfloor) φ(⌊gcd(a,b)n−c⌋) 种，所以考虑进行类似于埃式筛法的算法，每一次更新的时候将答案加上 lcm ( gcd ( a , b ) , c ) × φ ( ⌊ n − c gcd ( a , b ) ⌋ ) \operatorname{lcm}(\gcd(a,b),c)\times \varphi(\lfloor\frac{n-c} {\gcd(a,b)}\rfloor) lcm(gcd(a,b),c)×φ(⌊gcd(a,b)n−c⌋) 即可。
// 这回只花了45min就打完了。
// 真好。记得多手造几组。最好有暴力对拍。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10, mod = 1e9 + 7;
int phi[N]; // debug 这个地方要开 long long
bool not_prime[N];
int cnt, primes[N], n, ans = 0;
void sieve()
{
phi[1] = 1;
for (int i = 2; i < N; i ++)
{
if (!not_prime[i])
{
primes[++ cnt] = i;
phi[i] = i - 1;
}
for (int j = 1; i * primes[j] < N; j ++)
{
not_prime[i * primes[j]] = true; // debug i*primes[j] --> j*primes[j]
if (i % primes[j])
phi[i * primes[j]] = phi[i] * (primes[j] - 1);
else
{
phi[i * primes[j]] = phi[i] * primes[j];
break;
}
}
}
}
signed main()
{
cin >> n;
sieve();
for (int i = 1; i < n; i ++)
for (int j = 2 * i; j < n; j += i) // debug =n 的话没有法子选了
(ans += phi[j / i] * lcm(i, n - j) % mod) %= mod;
cout << ans << '\n';
return 0;
}
// 足下千里，移步换景，寰宇纷呈万花筒
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数