Description:

在平面直角坐标系中,四个端点为 的正方形称为单位正方形。之后我们考虑所有端点在 范围内的正方形,所有被其包含完全包含的单位正方形,都会被放上一个标记,问一共被放了多少个标记。


Solution:


由对称性不妨设 首先考虑如下绿色正方形:


令我们令外面的正方形的边长为 ,中间画出的小三角形的竖直边为 ,设其对答案的贡献为 ,那么:
$$f(L,i)=(L-2i)^2+2[i*(L-i)-L+gcd(i,L)]=L^2-2i*L+2i^2+2gcd(i,L)-2L$$
那么

,所以我们可以很容易的求出这些前缀和。之后我们只需要求出 表达式中的所有项的前缀和然后做到 询问就行了。