CodeForces 1717E【线性筛】

题意：给定 $n$，求所有三元组 $(a,b,c)$ 满足 $a+b+c=n$ 的 $\mathrm{lcm}(\gcd (a,b),c)$ 的和。

思想：

第一层循环枚举 $\gcd (a,b)$ 的值。

然后枚举 $a+b$ 的值。

容易发现，$a+b$ 的值一定是 $k\times \gcd (a,b)$，$k\in N^{\ast }$。

也就是说，$(a,b)$ 的取值方法一共有 $\phi (\lfloor \frac{n-c}{\gcd (a,b)}\rfloor )$ 种，所以考虑进行类似于埃式筛法的算法，每一次更新的时候将答案加上 $\mathrm{lcm}(\gcd (a,b),c)\times \phi (\lfloor \frac{n-c}{\gcd (a,b)}\rfloor )$ 即可。

// 这回只花了45min就打完了。
// 真好。记得多手造几组。最好有暴力对拍。

#include 

#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;
}

// 足下千里，移步换景，寰宇纷呈万花筒

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数
凑字数凑字数凑字数凑字数