510. 相切的圆(Tangent Circles)

圆A和圆B彼此相切，同时和直线L也分别相切，三个切点互不相同。圆C在A、B和L之间，且与这三者都相切，分别记圆A、B和C的半径为\(r_a,r_b,r_c\)：

对于所有满足\(0<r_a\le r_b\le n\)且\(r_a,r_b,r_c\)均为整数的可行解，我们定义\(S(n)=\sum(r_a+r_b+r_c)\)。对于\(0<r_a\le r_b\le5\)，唯一解是\(r_a=4,r_b=4,r_c=1\)，所以有\(S(5)=1+4+4=9\)，此外还已知\(S(100)=3072\)。求\(S(10^9)\)。

分析：题目中所列出的三圆与直线相切的情况实际上是笛卡尔定理的一种特殊情形，根据笛卡尔定理，三个圆的半径应满足以下关系：

则如要求\(r_c\)为整数，则\(r_ar_b\)应为完全平方数，同时观察上式，如把\(r_a,r_b\)同时扩大\(k\)倍也会导致\(r_c\)扩大\(k\)倍，如果\((r_a,r_b,r_c)\)是一组解，那么\((kr_a,kr_b,kr_c)\)也是一组解。则不妨设\(r_a=ku^2,r_b=kv^2\)且\(gcd(u,v)=1\)，则有\(r_{c} =\frac{k( uv)^{2}}{( u+v)^{2}}\)。因\(u,v\)互质，则\((uv)^2\)与\((u+v)^2\)互质，则\(k\)应是\((u+v)^2\)的倍数，则可设：

上式中\(m\le n\)且\(gcd(m,n)=1\)，此即为三个半径的通解，则我们可以通过遍历符合条件的\(m,n\)找到所有\(r_a,r_b,r_c\)的解。因题目要求\(0<r_a\le r_b\le10^9\)，且\(m\)总是小于等于\(n\)，则我们可以求得\(n\)最大的可能取值(对应\(q=1,m=1\))，则有：

当\(N=10^9\)时，有\(n\le177\)。因此我们只需要遍历\(1\le m \le n,1\le n\le177\)范围内的\(m,n\)值即可。当求得一个组基本解后，可以通过乘以\(k\)的方式得到另一组解，但需要保证\(kr_b\le10^9\)。这里还有一个技巧，当遍历不同的\(k\)值并加总时，可以把\((r_a+r_b+r_c)\)作为公因子提取出来，从而可以用求和公式简化计算，减少一次循环：

代码如下：

# time cost = 15.9 ms ± 254 µs

from math import gcd

def triplets(u,v):
    rc = (u*v)**2
    ra = ((u+v)*u)**2
    rb = ((u+v)*v)**2
    return rc,ra,rb

def main(n=10**9):
    res = 0
    u = int(((1+4*n**0.5)**0.5-1)/2)
    for j in range(1,u+1):
        for i in range(1,j+1):
            k = 1
            if gcd(i,j) == 1:
                rc,ra,rb = triplets(i,j)
                k = n // rb
                res += k*(k+1)*(rc+ra+rb)//2
    return res