P3601
不互质的数个数就是 \(n - \varphi(n)\)。
\(\displaystyle\varphi(n) = n\prod \frac{p_i - 1}{p_i}\)。
直接用小于 \(\sqrt{r}\) 的素数求欧拉函数。
所有数一起求。
rep(i, l, r) phi[i - l] = val[i - l] = i;
rep(i, 1, pcnt)for (LL j = (l + prm[i] - 1) / prm[i] * prm[i]; j <= r; j += prm[i])if (val[j - l] % prm[i] == 0) {phi[j - l] = phi[j - l] / prm[i] * (prm[i] - 1);while (val[j - l] % prm[i] == 0) val[j - l] /= prm[i];}
rep(i, l, r) if (val[i - l] != 1)phi[i - l] = phi[i - l] / val[i - l] * (val[i - l] - 1);
P2303
\[\begin{aligned}
\sum_{i = 1}^n \gcd(i, n)
&= \sum_{d|n}d\sum_{i = 1}^n[\gcd(i, n) = d] \\
&= \sum_{d|n}d\sum_{i = 1}^{\frac{n}{d}}\left[\gcd\left(i, \frac{n}{d}\right) = 1\right] \\
&= \sum_{d|n} d \times \varphi\left(\frac{n}{d}\right)
\end{aligned}
\]
\(\varphi\) 直接求。
P11218
引流
