中国剩余定理

{x≡a1(modm1)x≡a2(modm2)⋯x≡an(modmn)\begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \cdots \\ x \equiv a_n \pmod {m_n} \end{cases}

即计算x使得x满足上述条件

先决条件: ∀i∈{1,2,⋯n},∀j∈{1,2,⋯n},i≠j,gcd(i,j)=1\forall i\in\{1,2,\cdots n\}, \forall j\in \{1,2,\cdots n\}, i \ne j, gcd(i, j) = 1

定义:

Mi=∏i=1nmimiM_i = \frac{\prod_{i=1}^{n}{m_i}}{m_i}

定义: a模n意义下的逆元x:

ax≡1(modn),gcd(a,n)=1ax\equiv1\pmod{n},gcd(a,n)=1

计算方法(扩展欧几里得算法):

void exgcd(int a, int b, int &x, int &y) {
  if (b == 0) {
    a = 1;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
  // 递归计算, 具体说明略...
}
exgcd(a, n, x, y);

易知由于对于其他所有 njn_j, 其与 nin_i 互质, 与其不存在共同的大于1的因数, 因此其他所有 njn_j 的乘积自然与 nin_i 不存在相同的大于1的因数, 因此 gcd(mi,Mi)=1gcd(m_i, M_i) = 1
即 MiM_i 和 mim_i 互质，因此可以使用扩展欧几里得算法，计算出 tit_i, 使得 tiMi=1(modmi)t_i M_i = 1 \pmod{m_i}

因此, 定义:

x=∑i=1naitiMix = \sum_{i=1}^{n}{a_i t_i M_i}

因为:

∀i∈{1,2,⋯n},∀j∈{1,2,⋯ },i≠j,Mi=kmj(k>1,k∈N)\forall i\in\{1,2,\cdots n\}, \forall j\in\{1,2,\cdots\}, i\ne j, M_i = k m_j (k > 1, k\in\N)

所以:

∀j∈{1,2,⋯n},x=∑i=1naitiMi=ajtjMj=aj(modmj)\forall j\in\{1,2,\cdots n\}, x = \sum_{i=1}^{n}{a_i t_i M_i} = a_j t_j M_j = a_j \pmod{m_j}

即满足了题面条件
最小的答案即x, 结集为 x+km,k∈Nx + km, k\in\N

欧拉函数

首先定义欧拉函数 ϕ(n)\phi(n) 为小于等于 nn 与 nn 互质的数的数量
接下来证明欧拉函数具有积性, 即ϕ(nm)=ϕ(n)ϕ(m)\phi(nm)=\phi(n)\phi(m), 也即是ϕ(nm)\phi(nm)和ϕ(n)ϕ(m)\phi(n)\phi(m)存在双射关系
首先令n,m互质,

对于

{N=a(modn)N=b(modm)\begin{cases} N = a \pmod{n} \\ N = b \pmod{m} \end{cases}

首先根据欧拉函数的定义, N即ϕ(nm)\phi(nm)中某个数, NN与nmnm互质,
因此NN分别与n,mn,m互质,
因此中国剩余定理可行, 它恰好也要求互质
由上文，由于对于a,ba,b的t1,t2t_1,t_2是唯一的, 因此在k取0时, 即N\leq mn, N也是唯一的,
因此NN的数目也就是aa可能的数目和bb可能数目的乘积, 也就是t1t_1和t2t_2数目的乘积
证毕

接下来, 易知当n=pkn=p^k时

ϕ(pk)=pk−pk−1=(1−1p)pk=(1−1p)n\phi(p^k) = p^k-p^{k-1} = (1-\frac{1}{p})p^k = (1-\frac{1}{p})n

所以当

n=∏pikn = \prod_{}{p_{i}^{k}}

时, 将n的各个幂因子各自分散

ϕ(n)=∏(pi−1)piki−1=n∏(1−1pi)\phi(n) = \prod_{}{(p_i-1)p_{i}^{k_i-1}} = n\prod_{}{(1-\frac{1}{p_i})}

接下来引出ϕ(n)\phi(n)的若干性质
首先, 令p1p_1为nn的最小质因子, n1p1=nn_1 p_1=n

{n1≡0(modp1),ϕ(n)=p1n1∏(1−1pi)=ϕ(n1)p1n1≡k(modp1),ϕ(n)=ϕ(n1)ϕ(p1)=ϕ(n1)(p1−1)\begin{cases} n_1 \equiv 0 \pmod{p_1}, \phi(n) = p_1 n_1 \prod_{}{(1-\frac{1}{p_i})} = \phi(n_1)p_1 \\ %其他都有 n_1 \equiv k \pmod{p_1}, \phi(n) = \phi(n_1)\phi(p_1) = \phi(n_1)(p_1 - 1) %二者互质 \end{cases}

所以我们可以线性求欧拉函数, 因为欧拉筛每次都可以求出最小质因子

void work(int n) {
  vector<bool> vis(n + 1);
  vector<int> phi(n + 1), pri;
  for (int i = 2; i <= n; i++) {
    if (!vis[i]) {
      pri.push_back(i);
      phi[pri] = pri - 1;
    }
    for (auto p : pri) {
      if (i * p > n) break;
      vis[i * p] = true;
      // secondary division
      if (i % p == 0) {
        // i->n1, p->p1, 
        phi[i * p] = phi[i] * p;
      }
      phi[i * p] = phi[i] * phi[p]; // 积性
    }
  }
}

所以我们可以给出AC码

#include <bits/stdc++.h>
#define mod 666623333
#define int long long
#define N 1000001
using namespace std;

bitset<N> vis;
void solve() {
  int l, r;
  cin >> l >> r;
  
  vector<int> pri;
  for (int i = 2; i <= N; i++) {
    if (!vis[i]) {
      pri.push_back(i);
    }
    for (auto p : pri) {
      if (i * p > N) break;
      vis[i * p] = true;
      // i不适合作为因子了
      if (i % p == 0) break;
    }
  }
  vector<int> phi(N), minp(N);
  for (int i = l; i <= r; i++)
    phi[i - l] = i, minp[i - l] = i;
  for (int p : pri) {
    if (p * p > r) break;
    for (int x = (p - l % p) % p; x <= r - l; x += p) {
      // 依次计算贡献
      phi[x] = phi[x] / p * (p - 1);
      while (minp[x] % p == 0)
        minp[x] /= p;
    }
  }

  int ans = 0;
  for (int i = 0; i <= r - l; i++) {
    if (minp[i] > 1) phi[i] = phi[i] / minp[i] * (minp[i] - 1);
    ans = (ans + i + l - phi[i]) % mod;
  }
  cout << ans << '\n';
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  freopen("data.in", "r", stdin);
  freopen("data.out", "w", stdout);
  int _ = 1;
  while (_--) solve();
}