Project Euler 410
Project Euler 410
题目
Circle and tangent line
Let \(C\) be the circle with radius \(r, x^2 + y^2 = r^2\). We choose two points \(P(a, b)\) and \(Q(-a, c)\) so that the line passing through \(P\) and \(Q\) is tangent to \(C\).
For example, the quadruplet \((r, a, b, c) = (2, 6, 2, -7)\) satisfies this property.
Let \(F(R, X)\) be the number of the integer quadruplets \((r, a, b, c)\) with this property, and with \(0 < r \le R\) and \(0 < a \le X\).
We can verify that \(F(1, 5) = 10, F(2, 10) = 52\) and \(F(10, 100) = 3384\).
Find \(F(10^8, 10^9) + F(10^9, 10^8)\).
解决方案
令\(d=b-c, s=b+c.\)直线 \(PQ\) 的方向向量为\(\overrightarrow{PQ}=(-2a,c-b)=(-2a,-d),\)所以直线的斜率为 \(\dfrac{d}{2a}\)，过点 \((a,b)\) 的直线方程为\(2a(y-b)=d(x-a)\iff dx-2ay+a(2b-d)=0.\)
注意到\(2b-d=2b-(b-c)=b+c=s,\)于是直线可写成\(dx-2ay+as=0.\)原点到直线的距离为\(\dfrac{|as|}{\sqrt{d^2+(2a)^2}},\)相切要求该距离等于半径 \(r\)，因此\(\dfrac{|as|}{\sqrt{d^2+4a^2}}=r\iff a^2s^2=r^2(d^2+4a^2).\)即得到核心等式
\[ a^2(b+c)^2=r^2((b-c)^2+(2a)^2). \tag{1} \]
若 \(b=c\)，则 \(d=0\)，直线为 \(y=b\)，与圆相切当且仅当\(|b|=r.\)此时对每个 \((r,a)\) 都有两组解 \((b,c)=(r,r),(-r,-r)\)，因此贡献为\(2RX.\)
接下来只需统计 \(d\ne 0\) 的情况。
令\(t=\sqrt{d^2+4a^2}.\)由 \((1)\) 可得\(a^2s^2=r^2t^2.\)由于 \(a,r,s\) 都是整数，并且\(d^2+4a^2\)也是一个整数，那么必须有 \(t\in\mathbb Z\)，因此\((2a)^2+d^2=t^2,\)也就是说 \((2a,d,t)\) 构成勾股三元组。
进一步，由 \((1)\) 还得到
\[ as=\pm rt. \tag{2} \]
并且从\(b=\dfrac{s+d}{2}, c=\dfrac{s-d}{2}\)可知 \((b,c)\in\mathbb Z^2\) 当且仅当\(s\equiv d\pmod 2.\)
设\(u^2+v^2=w^2\)为原始勾股三元组，则存在互素且奇偶相反的 \(m>n\ge 1\) 使得\(u=m^2-n^2, v=2mn, w=m^2+n^2,\)或交换 \(u,v\)。
在我们的方程中，\(2a\) 必为偶数，因此分两类讨论：
\(2a\) 对应偶直角边
取\(2a=g\cdot 2mn, d=g(m^2-n^2), t=g(m^2+n^2),g\ge 1.\)则\(a=gmn.\)由 \((2)\) 得\(s=\pm \dfrac{rt}{a}=\pm \dfrac{r\cdot g(m^2+n^2)}{gmn}=\pm r\cdot\dfrac{m^2+n^2}{mn}.\)由于 \(\gcd(mn,m^2+n^2)=1\)（\(\gcd(m,n)=1\) 蕴含），故必须有\(mn\mid r.\)
令\(r=mn\cdot q, q\ge 1,\)则\(s=\pm q(m^2+n^2).\)而 \(m,n\) 奇偶相反，故 \(m^2-n^2\) 与 \(m^2+n^2\) 都为奇数，从而\(d=g(m^2-n^2)\equiv g\pmod 2, s\equiv q\pmod 2.\)由 \(s\equiv d\pmod 2.\) 得到唯一的额外约束\(g\equiv q\pmod 2.\)
那么，边界条件\(0<r\le R, 0<a\le X\)转化为\(q\le \left\lfloor\dfrac{R}{mn}\right\rfloor,g\le \left\lfloor\dfrac{X}{mn}\right\rfloor.\)
记\(A=\left\lfloor\dfrac{R}{mn}\right\rfloor,B=\left\lfloor\dfrac{X}{mn}\right\rfloor.\)满足 \(g\equiv q\pmod 2\) 的正整数对 \((q,g)\) 个数为“同奇偶的配对数”：
\[ N(A,B) =\left\lfloor\dfrac{AB+1}{2}\right\rfloor. \]
此外，\(d\) 可取正负、\(s\) 可取正负，二者独立，从而每对 \((q,g)\) 产生 \(4\) 个不同的 \((b,c)\)，因此该情形对固定的 \((m,n)\) 的贡献为
\[4\left\lfloor\dfrac{AB+1}{2}\right\rfloor.\]
注意：此情形中 \(mn\) 必为偶数（因 \(m,n\) 奇偶相反），因此只会覆盖偶数 \(mn\)。
\(2a\) 对应奇直角边（系数需要额外的 \(2\)）
取\(2a=2g(m^2-n^2), d=4gmn, t=2g(m^2+n^2),g\ge 1.\)于是\(a=g(m^2-n^2).\)由 \((2)\) 得\(s=\pm\frac{rt}{a}=\pm \dfrac{r\cdot 2g(m^2+n^2)}{g(m^2-n^2)}=\pm 2r\cdot\dfrac{m^2+n^2}{m^2-n^2}.\)由于 \(\gcd(m^2-n^2,m^2+n^2)=1\) 且 \(m^2-n^2\) 为奇数，因此必须有\(m^2-n^2\mid r.\)
令\(r=(m^2-n^2)\cdot q,\)则\(s=\pm 2q(m^2+n^2),\)此时 \(s\) 与 \(d\) 都为偶数，因此 \(s,d\)同奇偶恒成立，不再有奇偶配对限制。边界给出\(q\le \left\lfloor\dfrac{R}{m^2-n^2}\right\rfloor,g\le \left\lfloor\dfrac{X}{m^2-n^2}\right\rfloor,\)
故对固定的 \((m,n)\) 的贡献为
\[4\left\lfloor\dfrac{R}{m^2-n^2}\right\rfloor\left\lfloor\dfrac{X}{m^2-n^2}\right\rfloor.\]
并且这里的 \(m^2-n^2\) 恒为奇数。
以上两类恰好把所有 \(d\ne 0\) 的解按一个整数 \(k\) 分类：第一类产生 \(k=mn\)（必为偶数）；第二类产生 \(k=m^2-n^2=(m-n)(m+n)\)（必为奇数且两因子互素）。
二者共同特点是：\(k\) 都能写成\(k=uv, \gcd(u,v)=1,\)并且这种分解只由 \(k\) 的不同素因子分配决定。若\(\displaystyle{k=\prod_{i=1}^{\omega(k)}p_i^{e_i},}\)则在互素分解 \(k=uv\) 中，每个素因子 \(p_i^{e_i}\) 必须整体落在 \(u\) 或 \(v\) 的一边，因此互素分解的无序个数为\(2^{\omega(k)-1}.\)
而单位因子个数函数定义为\(\sigma_0^*(k)=2^{\omega(k)}.\)因此\(2^{\omega(k)-1}=\dfrac{\sigma_0^*(k)}{2}.\)
综合“每对分解对应 \(4\) 个符号选择”和上式，可将 \(d\ne 0\) 的总贡献写为对 \(k\) 的求和，并得到一个完全对称的公式。设\(N=\min(R,X).\)则
\[ F(R,X)=2RX+2\sum_{k=2}^{N}\sigma_0^*(k)\cdot T_k(R,X), \]
其中
\[ T_k(R,X)= \begin{cases} \left\lfloor\dfrac{R}{k}\right\rfloor\left\lfloor\dfrac{X}{k}\right\rfloor,& k\equiv1\pmod 2,\\ \left\lfloor\dfrac{\left\lfloor\dfrac{R}{k}\right\rfloor\left\lfloor\dfrac{X}{k}\right\rfloor+1}{2}\right\rfloor,& k\equiv0\pmod 2. \end{cases} \]
上面两式只通过 \(\lfloor R/k\rfloor,\lfloor X/k\rfloor\) 出现，因此立刻可见\(F(R,X)=F(X,R).\)
代码
1 |
|