包围整点

给定整数a,b，用$D(a, b)$表示抛物线$y=x^2$和直线$y=ax+b$所围成的闭区域： $$D(a,b)=\{(x, y): x^2\le y \le ax+b\}.$$ 令$L(a, b)$为$D(a, b)$中整点的数量，例如$L(1, 2)=8, L(2,-1)=1$。

再令$S(N)$为满足$|a|,|b|\le N$且$D(a, b)$的面积为有理数的所有$a,b$所对应的$L(a,b)$之和。

可以验证$S(5)=344, S(100)=26709528$。

求$S(10^{12})$的最后八位。

本题难度:

解答

令$x_1\le x_2$为两交点的横坐标，两式联立得 $$x^2-ax-b=0$$ 从而$x_1,x_2=a\pm\sqrt{a^2+4b}/2$，进一步可得 \begin{align*} D(a,b)&=\int_{x_1}^{x_2}(ax+b-x^2)dx \\ &=\left.(-\frac{1}{3}x^3+\frac{1}{2}ax^2+bx)\right|_{x_1}^{x_2} \\ &=-\frac{1}{3}(x_2^3-x_1^3)+\frac{a}{2}(x_2^2-x_1^2)+b(x_2-x_1) \\ &=(x_2-x_1)\left(-\frac{1}{3}(x_1^2+x_1x_2+x_2^2)+\frac{a}{2}(x_1+x_2)+b\right) \\ &=(x_2-x_1)\left(-\frac{1}{3}(x_1+x_2)^2-\frac{1}{3}x_1x_2+\frac{a}{2}(x_1+x_2)+b\right) \\ &=(x_2-x_1)\left(-\frac{1}{3}a^2+\frac{1}{3}b+\frac{a^2}{2}+b\right) \\ &=(x_2-x_1)(\frac{a^2}{6}+\frac{4}{3}b)。 \end{align*} 故当且仅当$x_2-x_1=\sqrt{a^2+4b}$为有理数时$D(a,b)$为有理数。令$c^2=a^2+4b$，由于a,b都是整数，所以若c是有理数，那么它也一定是整数。

此时又有$x_1,x_2=(a\pm c)/2$，在此范围内计数可得$L(a,b)=(c+1)(c^2-c+6)/6$。

在抛物线上枚举$x_1,x_2$的位置就可以确定$|c|=x_2-x_1$的值，由于$L(a,b)$之和c有关，因此事实上只需要确定每组c出现的次数，而这只和边界N有关。

汇总即得结果$18224771$。

f=lambda a,b,c:(b-c-1)*(4*a*a*a+6*a*a*(b+c)+2*a*(2*b*b+b*(2*c-1)+2*c*c+c+10)+b*b*b+b*b*(c-1)+b*(c*c+10)+c*c*c+c*c+10*c+24)//(-24)

g=lambda a,b,c:(2*a+1)*(b-c-1)*(b*(2*a*a+2*a+c*c+10)+2*(a*a+a+5)*c+b*b*b+b*b*(c-1)+c*c*c+c*c+24)//(-24)

n,m=10**12,10**6

print (m*(m+1)*(4*m**3+m**2+14*m+26)//15+sum(2*g(k,n//(k+1)+1,n//k) for k in range(1,m))-2*f(n,-1,1)+2*f(n,0,1)+(m+1)*(m*(2*m*(m+1)+5)+6)//6)%(10**8)