求
∑p∈Primen∑i=1n∑j=1[gcd(i,j)=p]
=∑p∈Prime⌊np⌋∑i=1⌊np⌋∑j=1[gcd(i,j)=1]
欧拉函数搞法:
=∑p∈Prime⌊np⌋∑i=12φ(i)−1
预处理欧拉函数前缀和即可。预处理时间复杂度O(n),单次询问O(n/lnn) ([1,n]中素数约有n/lnn个)
莫反搞法:
给第二个柿子来个传统艺能,即
=∑p∈Prime⌊np⌋∑i=1⌊np⌋∑j=1∑d|i,d|jμ(d)
=∑p∈Primen∑d=1μ(d)⌊np∗d⌋2
好像还是没法快速搞,因为和p,d都有关。令T=p∗d
n∑T=1∑p|T,p∈Primeμ(T/p)⌊nT⌋2
∑p|T,p∈Primeμ(T/p)的贡献可以枚举p预处理,然后数论分块即可。预处理O(nloglogn),单次询问O(√n)
万弘巨巨好厉害!
莫反tql
厉害, 一看就明白!
流批啊
献上% x 232个
万弘巨巨好厉害!
wh NB!