求
$$ \sum_{p\in Prime}\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=p] $$
$$ =\sum_{p\in Prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}[gcd(i,j)=1] $$

欧拉函数搞法：

$$ =\sum_{p\in Prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}2\varphi(i)-1 $$

预处理欧拉函数前缀和即可。预处理时间复杂度$\mathcal O(n)$,单次询问$\mathcal O(n/\ln n)$ ($[1,n]$中素数约有$n/\ln n$个)

code

莫反搞法：

给第二个柿子来个传统艺能，即
$$ =\sum_{p\in Prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{d|i,d|j}\mu(d) $$
$$ =\sum_{p\in Prime}\sum_{d=1}^n\mu(d)\lfloor\frac{n}{p*d}\rfloor^2 $$

好像还是没法快速搞，因为和$p,d$都有关。令$T=p*d$
$$ \sum_{T=1}^n\sum_{p|T,p\in Prime}\mu(T/p)\lfloor\frac{n}{T}\rfloor^2 $$
$\sum_{p|T,p\in Prime}\mu(T/p)$的贡献可以枚举$p$预处理，然后数论分块即可。预处理$\mathcal O(n\log \log n)$,单次询问$\mathcal O(\sqrt n)$

code