Table of Contents
题目
分析
有一个著名的“欧拉公式”，用来计算小于等于n的正整数中与n互质的数的个数，记作\(\varphi(n)\)。计算公式为：对于一个正整数n，若其质因数分解为\(n=p_1^{k_1}p_2^{k_2}...p_m^{k_m}\)，则：\(\varphi(n)=n\prod_{i=1}^m(1-\frac{1}{p_i})\)。当然本题要计算的，是与n不互质的数的个数，所以是\(n-\varphi(n)\)。
准备工作一：欧拉筛计算到\(\sqrt r\)的质数
这是一个常规的算法。其详细的解法可以参考P3383：线性筛素数。
根据题意，\(r\le 10^{12}\)，所以\(\sqrt r\le 10^6\)。
计算\(\varphi(n)\)
我们用两个数组来保存中间数据。一个是A[i]，存储某个数i的\(\varphi(i)\)。为了避免计算\(\frac{1}{p_i}\)可能出现的很小很小的数字，我们将其变形为：\((p_i-1) / p_i\)。
考虑更大的质因子
我们第一步准备工作中，只算到了\(\sqrt r\)的质因子，但可能还有比这大的质因子——但只可能有一个。我们还要考虑这个情况。我们用一个辅助数组B[i]来进行处理。方法是：
- 初始时，
A[i]=B[i]=i，也就是各自等于要计算\(\varphi(i)\)的那个i。 - 每次用一个\(p_i\)计算
A[i]的时候，不断将B[i]中对应的这个质因子去掉。 - 如果最后
B[i]==1，说明这个数字被之前的质因子分解完毕了。否则，还要计算一次，此时的质因子就是B[i]。
其他技巧
由于l和r本身值很大，但r-l（区间）较小，所以我们可以进行一个“偏移”映射，也就是\(l\Rightarrow 0, r\Rightarrow (r-l)\)。这样就避免了开一个巨大但十分稀疏的数组。
答案
思考
代码的45行，用B[i]^1来判断B[i]是不是等于1，这是一种古老的做法：因为在C时代，普遍认为这样的异或运算比纯比较运算要快一些。