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\) 直接求。