Project Euler 403
Project Euler 403
题目
Lattice points enclosed by parabola and line
For integers \(a\) and \(b\), we define \(D(a, b)\) as the domain enclosed by the parabola \(y = x^2\) and the line \(y = a\cdot x + b\):
\(D(a, b) = \{ (x, y) | x^2 \le y \le a\cdot x + b \}\).
\(L(a, b)\) is defined as the number of lattice points contained in \(D(a, b)\).
For example, \(L(1, 2) = 8\) and \(L(2, -1) = 1\).
We also define \(S(N)\) as the sum of \(L(a, b)\) for all the pairs \((a, b)\) such that the area of \(D(a, b)\) is a rational number and \(|a|,|b| \le N\).
We can verify that \(S(5) = 344\) and \(S(100) = 26709528\).
Find \(S(10^{12})\). Give your answer mod \(10^8\).
解决方案
交点由\(x^2=ax+b \Longleftrightarrow x^2-ax-b=0\)给出。判别式\(\Delta=a^2+4b.\)两实根（若存在）为\(x_0=\dfrac{a-\sqrt{\Delta}}2, x_1=\dfrac{a+\sqrt{\Delta}}2, x_0\le x_1.\)
在区间 \([x_0,x_1]\) 上，直线在抛物线之上，且\(ax+b-x^2=-(x-x_0)(x-x_1)=(x-x_0)(x_1-x)\ge 0.\)那么有面积：\(\displaystyle{A(D)=\int_{x_0}^{x_1} (ax+b-x^2)dx=\int_{x_0}^{x_1} (x-x_0)(x_1-x)dx.}\)
令 \(d=x_1-x_0\)，作平移 \(x=x_0+u\)（\(u\in[0,d]\)），则被积函数变为 \(u(d-u)\)，因此
\[ A(D)=\int_0^d u(d-u)du=\frac{d^3}{6}, d=x_1-x_0=\sqrt{\Delta}. \]
因为 \(a,b\in\mathbb Z\Rightarrow \Delta\in\mathbb Z\)，所以 \(\sqrt{\Delta}\) 要么为整数，要么为无理数；面积为有理数当且仅当 \(\sqrt{\Delta}\in\mathbb Z\)，即 \(\Delta\) 为完全平方数。
此外，若 \(\Delta\) 为平方数，则\(\Delta\equiv a^2\pmod 4 \Rightarrow \sqrt{\Delta}\equiv a\pmod 2,\)从而 \((a\pm \sqrt{\Delta})/2\in\mathbb Z\)，也就是说两交点横坐标 \(x_0,x_1\) 必为整数。
因此，题目要求的 \((a,b)\) 等价于满足 \(|a|,|b|\le N\) 且\(a^2+4b=d^2(\exists d\in\mathbb Z_{\ge 0})\)的所有整数对。
在交点都是整数的前提下，对每个整数 \(x\in[x_0,x_1]\cap\mathbb Z\)，纵向可取的整数 \(y\) 的个数为
\(\#\{y\in\mathbb Z\mid x^2\le y\le ax+b\}= (ax+b-x^2)+1.\)因此\(\displaystyle{L(a,b)=\sum_{x=x_0}^{x_1} ((ax+b-x^2)+1).}\)
利用分解\(ax+b-x^2=(x-x_0)(x_1-x),\)令 \(d=x_1-x_0\)，写 \(x=x_0+i\)（\(i=0,1,\dots,d\)），则\(ax+b-x^2=i(d-i).\)于是\(\displaystyle{L(a,b)=\sum_{i=0}^d (i(d-i)+1)=(d+1)+\sum_{i=0}^d (id-i^2).}\)
而根据恒等式\(\displaystyle{\sum_{i=0}^d i=\frac{d(d+1)}2,\sum_{i=0}^d i^2=\frac{d(d+1)(2d+1)}6,}\)代入得
\[ L(a,b)= (d+1)+d\cdot \frac{d(d+1)}2-\frac{d(d+1)(2d+1)}6 =\frac{d^3+5d+6}{6} =1+\frac{d(d^2+5)}6. \]
记\(g(d)=1+\dfrac{d(d^2+5)}6 (d\in\mathbb Z_{\ge 0}),\)则只要面积有理（等价于交点差 \(d\) 为整数），就有 \(L(a,b)=g(d)\)。
对 \(x^2-ax-b=0\)，由韦达定理得：\(x_0+x_1=a, x_0x_1=-b.\)所以在“面积有理”的情形中，\((a,b)\) 与整数交点对 \((x_0,x_1)\)（取 \(x_0\le x_1\)）一一对应，且约束变为\(|x_0+x_1|\le N, |x_0x_1|\le N,\)贡献为 \(g(x_1-x_0)\)。
因此 \[ S(N)=\sum_{\substack{x_0\le x_1\\ |x_0+x_1|\le N\\|x_0x_1|\le N}} g(x_1-x_0). \]
由 \(|x_0x_1|\le N\)，若 \(|x_0|>\sqrt N\) 且 \(|x_1|\ge |x_0|\)，则必有 \(|x_0x_1|>N\)，因此只需枚举较小绝对值的端点到\(\lfloor\sqrt N\rfloor\)。令 \(q=\lfloor\sqrt N\rfloor\)。再定义前缀和\(\displaystyle{G(n)=\sum_{d=0}^n g(d).}\)
用三角数 \(t=\dfrac{n(n+1)}2\) 可化简：
\[ G(n)=\sum_{d=0}^n\left(1+\frac{d(d^2+5)}6\right) =(n+1)+\dfrac{1}{6}\left(\sum_{d=0}^n d^3+5\sum_{d=0}^n d\right) =(n+1)+\dfrac{t^2+5t}{6}. \]
下面分两类进行考虑：
两交点同号（含 0）
先只算 \((x_0,x_1)=(u,v)\) 且 \(0\le u\le v\)。
此时\(a=u+v, b=-uv, d=v-u,\)约束变为\(u+v\le N, uv\le N.\)固定 \(u\)，则 \(v\) 取值为\(v=u,u+1,\dots,v_{\max},\)其中\(v_{\max}=\min(N-u,\lfloor N/u\rfloor)(u\ge 1),\)而 \(u=0\) 时仅有 \(v\le N\)。
因此该 \(u\) 的贡献为
\[ \sum_{v=u}^{v_{\max}} g(v-u)=\sum_{d=0}^{v_{\max}-u} g(d)=G(v_{\max}-u). \]
因此令\(\displaystyle{W_1=\sum_{u=0}^{q} G(\min(N-u,\lfloor N/u\rfloor)-u),}\)其中 \(u=0\) 项按 \(G(N)\) 处理（因为 \(v_{\max}=N\)）。
同号的负象限 \((x_0,x_1)=(-v,-u)\) 给予 \((a,b)\mapsto(-a,b)\)，贡献完全相同，所以整体乘 2；但 \((u,v)=(0,0)\) 的 \(a=0\) 在镜像下不变，会被乘 2 多算一次，需要减去 \(g(0)=1\)。故同号总贡献为\(2W_1-1.\)
两交点异号
取 \((x_0,x_1)=(-u,v)\)，其中 \(u,v>0\)。则\(a=v-u, b=uv, d=v-(-u)=u+v.\)约束：
- \(|b|=uv\le N\)；
- \(|a|=|v-u|\le N\) 在 \(uv\le N\) 下自动成立（因为 \(u,v\le N\)）。
为了避免把 \((u,v)\) 与 \((v,u)\)（对应 \(a\) 正负互换）重复计数，先只取 \(u\le v\)。固定 \(u\)，则 \(v=u,\dots,\lfloor N/u\rfloor\)。
该 \(u\) 的贡献为
\[ \sum_{v=u}^{\lfloor N/u\rfloor} g(u+v) =\sum_{d=2u}^{u+\lfloor N/u\rfloor} g(d) =G\left(u+\left\lfloor \frac{N}{u}\right\rfloor\right)-G(2u-1). \]
令\(\displaystyle{W_2=\sum_{u=1}^{q}\left(G\left(u+\left\lfloor \frac{N}{u}\right\rfloor\right)-G(2u-1)\right).}\)把 \(a\leftrightarrow -a\) 的对称性乘 \(2\) 得到 \(2W_2\)，但当 \(u=v\) 时 \(a=0\) 不成对，会被乘 \(2\) 多算一次，需要减去对角\(\displaystyle{d=\sum_{u=1}^{q} g(2u).}\)因此异号总贡献为\(2W_2-d.\)
综上所述，
\[ S(N)=(2W_1-1)+(2W_2-d). \]
代码
1 | from tools import int_sqrt |