Warm-up problem

Chinese Remainder Theorem

$$\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}$$

That is, calculate x such that x satisfies the above conditions

Prerequisites: $\forall i\in\{1,2,\cdots n\}, \forall j\in \{1,2,\cdots n\}, i \ne j, gcd(i, j) = 1$

Definition:

$$M_i = \frac{\prod_{i=1}^{n}{m_i}}{m_i}$$

Definition: The modular inverse x of a modulo n:

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

Calculation method (Extended Euclidean Algorithm):

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;
  // Recursive calculation, detailed explanation omitted...
}
exgcd(a, n, x, y);

It is easy to see that since all other $n_j$ are coprime to $n_i$ and share no common factors greater than 1 with it, the product of all other $n_j$ naturally shares no common factors greater than 1 with $n_i$, thus $gcd(m_i, M_i) = 1$
That is, $M_i$ and $m_i$ are coprime, so we can use the Extended Euclidean Algorithm to calculate $t_i$, such that $t_i M_i = 1 \pmod{m_i}$

Therefore, define:

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

Because:

$$\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)$$

Therefore:

$$\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}$$

Which satisfies the problem conditions
The minimum answer is x, and the solution set is $x + km, k\in\N$

Euler’s Totient Function

First, define Euler’s totient function $\phi(n)$ as the number of positive integers less than or equal to $n$ that are coprime to $n$
Next, we prove that Euler’s totient function is multiplicative, i.e., $\phi(nm)=\phi(n)\phi(m)$, which means there is a bijection between $\phi(nm)$ and $\phi(n)\phi(m)$
First, let n, m be coprime,

For

$$\begin{cases} N = a \pmod{n} \\ N = b \pmod{m} \end{cases}$$

First, by the definition of Euler’s totient function, N is a number counted in $\phi(nm)$, and $N$ is coprime to $nm$,
Therefore, $N$ is coprime to $n$ and $m$ respectively,
Therefore, the Chinese Remainder Theorem is applicable, as it also happens to require coprimality
From the above, since $t_1, t_2$ for $a, b$ are unique, when k is 0, i.e., N\leq mn, N is also unique,
Therefore, the number of $N$ is the product of the number of possible $a$’s and the number of possible $b$’s, which is the product of the number of $t_1$’s and $t_2$’s
Q.E.D.

Next, it is easy to see that when $n=p^k$

$$\phi(p^k) = p^k-p^{k-1} = (1-\frac{1}{p})p^k = (1-\frac{1}{p})n$$

So when

$$n = \prod_{}{p_{i}^{k}}$$

, separating each prime power factor of n

$$\phi(n) = \prod_{}{(p_i-1)p_{i}^{k_i-1}} = n\prod_{}{(1-\frac{1}{p_i})}$$

Next, we introduce several properties of $\phi(n)$
First, let $p_1$ be the smallest prime factor of $n$, $n_1 p_1=n$

$$\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}$$

So we can calculate Euler’s totient function linearly, because the Euler sieve can find the smallest prime factor each time

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]; // Multiplicative
    }
  }
}

So we can give the AC code

#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 is no longer suitable as a factor
      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) {
      // Calculate contribution in turn
      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();
}