P3601 签到题

一. 思路

1≤l≤r≤10121 \le l \le r \le 10^{12}，r−l≤106r-l \le 10^6。很显然，传统的用欧拉函数是积性函数这条性质的从 11 扫到区间右端的方法肯定不行。
虽然传统的方法不行。但欧拉函数还有一条有用的公式：φ(n)=n×∏i=1npi−1pi\varphi(n)=n \times \prod\limits_{i=1}^{n}\dfrac{p_i-1}{p_i} 。也就是说，我们只要知道 l∼rl \sim r 中所有数的质因数分解就好了。不难发现一个数 nn 的质因数中有一个或零个大于 n\sqrt{n} 。那么我们把小于等于 r\sqrt{r} 的质数姑且称为“小质数”；大于 r\sqrt{r} 的叫“大质数”。

先预处理出所有小质数（也就是 1∼1061 \sim 10^6 内的）开一个数组 invinv 每个位置预处理为下标的值（就是 φ(n)=n×∏i=1npi−1pi\varphi(n)=n \times \prod\limits_{i=1}^{n}\dfrac{p_i-1}{p_i} 中的等式右边的 nn），然后用倍数法枚举所有小质数在 l∼rl \sim r 区间中的倍数，将相应的 inviinv_i 乘上 ∏i=1npi−1pi\prod\limits_{i=1}^{n}\dfrac{p_i-1}{p_i}。

当然，不要忘了大质数，因为每个数至多有一个大质数，所以大质数也很好处理。开一个数组 bidprimebidprime 全初始化为下标。用倍数法枚举 primeiprime_i 的倍数枚举到相应的 invjinv_j 时，顺便把 bigprimejbigprime_j 中所有的的因数 primeiprime_i 剔除。最后就得到了每个数的大质数。

二. 细节

最重要的细节就是枚举小指数的倍数时从几枚举了。设该小质数为 pp，区间左端点为 ll 。答案是 max⁡{p2,⌈lp⌉×p}\max\{ p^2, \left\lceil\dfrac{l}{p}\right\rceil \times p \}。

为什么呢？首先小于 p2p^2 的 pp 的倍数在枚举 22，33 等比它更小的质数时就已经枚举过了。而 $\left\lceil\dfrac{l}{p}\right\rceil \times p $ 是大于等于 ll 的第一个 pp 的倍数。

三. 代码

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
52
53
54
#include<cstdio>
#include<cmath>
#define re register 
#define int long long
const int MAXprime = 1e6;
const int MAXn = 1e6;
const int MOD = 666623333;

template <class T>
inline T max(T a, T b) {
    return a > b ? a : b;
}

int cntp, prime[MAXprime / 5 + 100];
bool notp[MAXprime + 10];
void PrimeSieve(int up) {						//线性筛不解释 
    notp[1] = 1;
    for (re int i = 2; i <= up; ++i) {
        if (!notp[i]) 
            prime[++cntp] = i;
        int upj = up / i;
        for (re int j = 1; j <= cntp && prime[j] <= upj; ++j) {
            notp[i * prime[j]] = 1;
            if (!(i % prime[j])) 
                break;
        }
    }
}

int ans, l, r, phi[MAXn + 10], bigprime[MAXn + 10];
signed main() {
    PrimeSieve(MAXprime);
    scanf("%lld %lld", &l, &r);
    for (re int i = l; i <= r; ++i) {			//初始化 
        phi[i - l] = bigprime[i - l] = i;
    }
    for (re int i = 1; i <= cntp; ++i) {		//倍数法：枚举所有小质数的倍数 
        for (re int j = max(prime[i] * prime[i], (int)ceil((double)l / prime[i]) * prime[i]); j <= r; j += prime[i]) {
            phi[j - l] = phi[j - l] / prime[i] * (prime[i] - 1);
            while (!(bigprime[j - l] % prime[i])) {
                bigprime[j - l] /= prime[i];
            }
        }
    }
    for (re int i = l; i <= r; ++i) {			//处理大质数 
        if (bigprime[i - l] > 1) {
            phi[i - l] = phi[i - l] / bigprime[i - l] * (bigprime[i - l] - 1);
        }
    }
    for (re int i = l; i <= r; ++i) {			//求和 
        ans = (ans + i - phi[i - l]) % MOD;
    }
    printf("%lld\n", ans);
}