P3601. 签到题

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 322 阅读时长 ≈ 1 分钟

考点

  • 欧拉函数

题解

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LEN = 1e7 + 50, MOD = 666623333;
bitset<LEN> vis;
ll l, r, tot, pri[LEN], arr[LEN], phi[LEN];

void init() {
  cin >> l >> r;
  // 欧拉筛1e6以内的质数
  for (ll i = 2; i <= 1e6; ++i) {
    if (!vis[i]) pri[++tot] = i;
    for (int j = 1; j <= tot && 1ll * i * pri[j] <= 1e6; ++j) {
      vis[i * pri[j]] = 1;
      if (i % pri[j] == 0) break;
    }
  }
  // arr记录原始值，phi记录欧拉函数
  for (ll i = l; i <= r; ++i) arr[i - l] = phi[i - l] = i;
}

int main() {
  init();
  // 区间筛求欧拉函数
  for (int i = 1; i <= tot; ++i) {
    int p = pri[i];
    for (ll j = max(2ll, (l - 1) / p + 1) * p; j <= r; j += p) {
      phi[j - l] = phi[j - l] / p * (p - 1);
      while (arr[j - l] % p == 0) arr[j - l] /= p;
    }
  }
  ll ans = 0;
  for (ll i = l; i <= r; ++i) {
    if (arr[i - l] > 1) phi[i - l] = phi[i - l] / arr[i - l] * (arr[i - l] - 1);
    ans = (i - phi[i - l] + ans) % MOD;  // 减掉互质的个数就等于不互质的个数了
  }
  cout << ans;
  return 0;
}

思路

欧拉函数的模板题，但因为数据规模过大，不可能用线性筛的方式去求；只能采取区间筛结合欧拉函数定义来算

设\(p\)代表质因子，那么有\(n={p_1}^{k_1}{p_2}^{k_2}\cdots {p_m}^{k_m}\)

有\(\varphi \left( n \right) ={p_1}^{k_1-1}\left( p_1-1 \right) {p_2}^{k_2-1}\left( p_2-1 \right) \cdots {p_m}^{k_m-1}\left( p_m-1 \right)\)