idy又开坑辣。
mobius反演题么么哒。强行sqrt(n)的询问。
于是推一下式子。
answer = ∑i∑j1 (gcd(i, j) = 1)
= ∑<sub>p</sub>∑<sub>g</sub>u(g) * (n/(p*g)) * (m/(p*g))
然后把p和g合起来设为v。
h(v) = ∑ u(v) (v = x/p)
然后发现h(v)函数是很好推的。
h(px) = (x % p == 0) ? (u(x)) : (u(x) - h(x))
然后就搞定啦orz.