0410 圆与切线
* * * *
拉格朗日计划
* * * *
圆与切线

记C为$x^2+y^2=r^2$所表示的圆,取两点$P(a, b)$和$Q(-a, c)$,使得过PQ的直线与圆C相切。

例如$(r, a, b, c)=(2, 6, 2, -7)$就能满足上述要求。

记$F(R, X)$是满足$0 < r\le R, 0< a\le X$的整数四元组$(r, a, b, c)$的总数。

可以验证$F(1, 5)=10, F(2,10)=52, F(10, 100)=3384$。

求$F(10^8, 10^9)+F(10^9, 10^8)$。

本题难度:



解答

设切点是$(x_0,y_0)$,则 $$x_0^2+y_0^2=r^2$$ 切线方程是 $$x_0x+y_0y=r^2$$ 将P和Q的坐标代入切线方程有 $$ax_0+by_0=r^2, \quad -ax_0+cy_0=r^2.$$ 几式联立并小区$x_0,y_0$即得 $$r^2(4a^2+(b-c)^2)=a^2(b+c)^2.$$ 从而$4a^2+(b-c)^2$是完全平方数,亦即$2a, b-c$是勾股数,用欧几里得法枚举勾股数,再检验能否符合上式。解集可以由 \begin{align*} r&=umn \\ a&=vmn \\ b&=\pm u(m^2+n^2) \\ c&=\pm v(m^2-n^2) \end{align*} 刻画。枚举m,n并计数即可,最终结果是$799999783589946560$。

注:因用到math.gcd函数和fstring格式化输出,以下代码为Python 3,且代码中打印了进度信息。

import math

m,n=10**9,10**8
bound=10**4
res=0
tick=100
for a in range(1,bound+1):
    b=a+1
    while a*b<=n:
        if math.gcd(a,b)==1:
            c=(m//a//b)*(n//a//b)
            res+=c if (a%2==b%2) else (c+1)//2
        b+=1
    if a < tick:
        print(f"{a/tick:.2f} percent completed")
    if a%tick==0:
        print(a//tick,"percent completed")
print(4*m*n+8*res)