题解 P3601 【签到题】
Jayun
2020-08-13 18:41:08
# 题目大意：
求 $\sum_{i=l}^{r}(i-\varphi(i))\mod 666623333$。
# 正文：
## 方法一：
预处理出所有的欧拉函数值，直接求 $\sum_{i=l}^{r}(i-\varphi(i))\mod 666623333$。但是 $1\leq l\leq r\leq 10^{12}$，只能过 60% 的数据。
## 方法二：
发现数据 $r-l\leq 10^6$，这是一个很不错的切入点。为了得到欧拉函数值，先筛出 $\sqrt{r}=10^6$ 内所有质数，统计每个质数对 $[l,r]$ 内所有欧拉函数值的贡献。
# 法二代码：
```cpp
ll pri[N], cnt, phi[N], A[N], ans;
bool vis[N];
void Prime ()
{
for (int i = 2; i <= N - 10; i++)
{
if(!vis[i]) pri[++cnt] = i;
for (int j = 1; j <= cnt && i * pri[j] <= N - 10; j++)
{
vis[pri[j] * i] = 1;
if(!(i % pri[j])) break;
}
}
}
int main()
{
Prime();
scanf ("%lld%lld", &l, &r);
for (ll i = l; i <= r; i++)
phi[i - l] = i, A[i - l] = i;
for (int i = 1; i <= cnt && pri[i] * pri[i] <= r; i++)
{
ll pr = pri[i], start = l;
if (l % pr) start = l / pr * pr + pr;
for (ll j = start; j <= r; j += pr)
{
phi[j - l] = phi[j - l] / pr * (pr - 1);
while(A[j - l] % pr == 0) A[j - l] /= pr;
}
}
for (ll i = l; i <= r; i++)
{
if(A[i - l] > 1)
phi[i - l] = phi[i - l] / A[i - l] * (A[i - l] - 1);
ans = (ans + (i - phi[i - l]) % mod) %mod;
}
printf ("%lld", ans);
return 0;
}
```