一、 题目描述

题目背景

这是一道签到题！建议做题之前仔细阅读数据范围！

题目描述

我们定义一个函数：$\operatorname{qiandao}(x)$ 为小于等于 $x$ 的数中，与 $x$ 不互质的数的个数。

这题作为签到题，给出 $l$ 和 $r$，求出：

$$\left(\sum_{i=l}^r \operatorname{qiandao}(i) \right) \bmod 666623333$$

数据范围

• 对于 30% 的数据，$l,r\leq 10^3$。
• 对于 60% 的数据，$l,r\leq 10^7$。
• 对于 100% 的数据，$1 \leq l \leq r \leq 10^{12}$，$r-l \leq 10^6$。

---

二、 前置考点：欧拉函数 $\varphi(n)$

欧拉函数的核心计算公式为：

$$\varphi(n) = n \times \left(1 – \frac{1}{p_1}\right) \times \left(1 – \frac{1}{p_2}\right) \times \dots \times \left(1 – \frac{1}{p_m}\right)$$

这里提供两种推导视角：

方法一：从“质数幂”到“积性”（最优雅的证法）

第一步：只看单一质数的幂 $p^k$

假设我们要求 $\varphi(p^k)$，也就是在 $1$ 到 $p^k$ 这 $p^k$ 个数中，有多少个数与 $p^k$ 互质？

• 与 $p^k$ 不互质的数，必然包含质因子 $p$。
• 在 $1$ 到 $p^k$ 中，$p$ 的倍数有：$p, 2p, 3p, \dots, p^{k-1} \cdot p$。
• 这样的数一共有 $p^{k-1}$ 个。
• 因此，与 $p^k$ 互质的数，就是总数减去这些倍数：$$\varphi(p^k) = p^k – p^{k-1} = p^k \left(1 – \frac{1}{p}\right)$$

第二步：利用欧拉函数的“积性”

欧拉函数是一个积性函数。在数论中，这意味着：如果两个数 $a$ 和 $b$ 互质（即 $\gcd(a, b) = 1$），那么：

$$\varphi(a \times b) = \varphi(a) \times \varphi(b)$$

第三步：拼合起来得到最终公式

我们已知 $n$ 的唯一分解定理形式：

$$n = p_1^{k_1} \times p_2^{k_2} \times \dots \times p_m^{k_m}$$

因为不同的质数之间没有公约数，所以各个 $p_i^{k_i}$ 之间显然是两两互质的。根据积性函数的性质，我们可以把它们拆开：

$$\varphi(n) = \varphi(p_1^{k_1}) \times \varphi(p_2^{k_2}) \times \dots \times \varphi(p_m^{k_m})$$

代入我们在第一步推导出的公式，得到：

$$\varphi(n) = p_1^{k_1}\left(1 – \frac{1}{p_1}\right) \times p_2^{k_2}\left(1 – \frac{1}{p_2}\right) \times \dots \times p_m^{k_m}\left(1 – \frac{1}{p_m}\right)$$

利用乘法的交换律，把前面所有的 $p_i^{k_i}$ 乘在一起，正好等于 $n$：

$$\varphi(n) = (p_1^{k_1} \dots p_m^{k_m}) \times \left(1 – \frac{1}{p_1}\right) \dots \left(1 – \frac{1}{p_m}\right)$$

$$\varphi(n) = n \times \left(1 – \frac{1}{p_1}\right) \times \left(1 – \frac{1}{p_2}\right) \times \dots \times \left(1 – \frac{1}{p_m}\right)$$

方法二：容斥原理（最贴近直觉的证法）

如果在 $1$ 到 $n$ 中找出与 $n$ 互质的数，等价于剔除掉所有含有 $p_1, p_2, \dots, p_m$ 因子的数。利用韦恩图的容斥原理思想：

1. 总数： 一共有 $n$ 个数。
2. 剔除单倍数：
   • $p_1$ 的倍数有 $\frac{n}{p_1}$ 个，剔除。
   • $p_2$ 的倍数有 $\frac{n}{p_2}$ 个，剔除。
   • 算式变为：$n – \frac{n}{p_1} – \frac{n}{p_2} – \dots$
3. 加回多减的交集：
   • 既是 $p_1$ 又是 $p_2$ 的倍数（即 $p_1 \times p_2$ 的倍数）被减了两次，需加回一次，共 $\frac{n}{p_1 p_2}$ 个。
   • 算式变为：$n – \sum \frac{n}{p_i} + \sum \frac{n}{p_i p_j}$
4. 依次类推（加加减减）：
   • 减去三个质数乘积的倍数，加回四个质数乘积的倍数……

最终，互质数的总个数长算式为：

$$\varphi(n) = n – \left( \frac{n}{p_1} + \frac{n}{p_2} + \dots \right) + \left( \frac{n}{p_1 p_2} + \frac{n}{p_1 p_3} + \dots \right) – \dots$$

提取 $n$：

$$\varphi(n) = n \times \left[ 1 – \left( \frac{1}{p_1} + \frac{1}{p_2} + \dots \right) + \left( \frac{1}{p_1 p_2} + \frac{1}{p_1 p_3} + \dots \right) – \dots \right]$$

如果展开多项式乘积 $\left(1 – \frac{1}{p_1}\right) \dots \left(1 – \frac{1}{p_m}\right)$，结果一字不差地等于方括号内的容斥原理式子。因此完美折叠为连乘形式：

$$\varphi(n) = n \prod_{i=1}^m \left(1 – \frac{1}{p_i}\right)$$

---

三、 解题思路

1. 预处理素数：先用线性筛找出 $\le \sqrt{r}$（即 $10^6$ 范围内）的所有素数。
2. 区间映射（数组偏移）：由于 $l$ 和 $r$ 数值高达 $10^{12}$，但区间长度 $r-l \le 10^6$，将庞大的数字 $i$ 映射到数组下标 $i-l$ 上进行处理。
3. 区间埃氏筛：初始化 phi 数组和余数 rem 数组为原本的数字。寻找 $\ge l$ 的最小的 $p$ 的倍数作为起点，对区间内每一个倍数，使用公式 phi = phi / p * (p - 1) 更新互质数的个数，同时在 rem 中不断除以 $p$ 来剥离质因子。
4. 大质数特判：遍历结束后，如果有 rem > 1，说明残留了一个大于 $\sqrt{r}$ 的大质数因子，需要对其补上最后一次修正计算。
5. 累加统计：根据题意计算不互质的个数 x - phi，累加并取模输出。

---

四、 AC 代码

C++

// Sunshine, sunshine, ladybugs awake!
// Clap your hooves and do a little shake!
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

using PII=pair<int,int> ;

const int mod=666623333;
const int MAXN=1000005;

bitset<MAXN> is_prime; 
vector<int> primes;
int min_factor[MAXN];       // 记录最小质因子
int omega[MAXN];            // 记录不同质因子的种数

/* =================  线性筛初始化  ================= */
void init_sieve() {
    is_prime.set();                   // 先全部标记为质数
    is_prime[0] = is_prime[1] = false;
    
    for (int i = 2; i < MAXN; ++i) {
        if (is_prime[i]) {            // i 是质数
            primes.push_back(i);
            min_factor[i] = i;
            omega[i]    = 1;
        }
        /* 用当前质数去筛合数 */
        for (int p : primes) {
            if (i * p >= MAXN) break;
            is_prime[i * p] = false;
            min_factor[i * p] = p;
            
            if (i % p == 0) {
                omega[i * p] = omega[i]; // p 已经是 i 的质因子，种类数不增加
                break;                   // 保证只被最小质因子筛
            } else {
                omega[i * p] = omega[i] + 1; // p 是新的质因子，种类数 +1
            }
        }
    }
}

void solve() {
    int l, r;
    cin >> l >> r;
    
    int len = r - l + 1;
    vector<int> phi(len);
    vector<int> rem(len);
    
    for(int i = 0; i < len; i++){
        phi[i] = l + i;
        rem[i] = l + i;
    }
    
    for(auto p : primes){
        if(p * p > r) break;
        
        int st = (l + p - 1) / p * p;
        for(int i = st; i <= r; i += p){
            int idx = i - l;
            phi[idx] = phi[idx] / p * (p - 1);
            
            while(rem[idx] % p == 0){
                rem[idx] /= p;
            }
        }
    }
    
    int ans = 0;
    for(int i = 0; i < len; i++){
        if(rem[i] > 1){
            phi[i] = phi[i] / rem[i] * (rem[i] - 1);
        }
        
        int curr = l + i;
        ans = (ans - phi[i] + curr) % mod;
    }
    
    cout << ans << endl;
}

signed main() { 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    init_sieve();
    //int t;cin >> t;while (t--) 
    solve();
    return 0;
}