0195 内切圆
* * * *
拉格朗日计划
* * * *
内切圆

称三边长度都为整数、且恰好有一个角为60度的三角形为60度三角形。

内切圆半径不超过100的60度三角形共有1234个。

记$T(n)$为内切圆半径不超过n的60度三角形的总数,可以验证 $$T(100)=1234, \quad T(1000)=22767, \quad T(10000)=359912.$$ 求$T(1053779)$。

本题难度:



解答

本题和第143题类似,设a,b,c分别是三角形的三边,其中a,b的夹角为60度,那么由余弦定理可得 $$a^2+b^2-ab=c^2$$ 同样根据此帖中的内容,满足上式的a,b,c可以由以下类似欧几里得公式的方法生成: $$a=(2mn+n^2)k, \quad b=(2mn+m^2)k, \quad c=(m^2+n^2+mn)k, $$ 或 $$a=(m^2-n^2)k, \quad b=(2mn+m^2)k, \quad c=(m^2+n^2+mn)k,$$ 其中m,n,k都是正整数、m,n互素、$m>n$且$m-n$不能被3整除。

若记S为三角形的面积,C为三角形的周长,r为内切圆的半径,则有 $$r=\frac{2S}{C}=\frac{ab\sin 60^{\circ}}{a+b+c}=\frac{\sqrt3ab}{2(a+b+c)}.$$ 在$a=(2mn+n^2)k$时有 $$r=\frac{\sqrt3}{2}\cdot\frac{(2mn+n^2)(2mn+m^2)k}{2m^2+2n^2+5mn}=\frac{\sqrt3 k}{2}\cdot\frac{mn(2m+n)(2n+m)}{(2m+n)(m+2n)}=\frac{\sqrt3}{2}mnk.$$ 在$a=(m^2-n^2)k$时有 $$r=\frac{\sqrt3}{2}\cdot\frac{(m^2-n^2)(2mn+m^2)k}{3m^2+3mn}=\frac{1}{2\sqrt 3}(m-n)(2n+m)k.$$ 枚举m,n,注意前一种情况从m开始枚举,后一种情况从n开始枚举,结果是$75085391$。

import math,fractions

target=1053779
q=math.sqrt(3)

x=0

m=2
while m < int(2.0*target/q)+1:
    n=r=1
    while n < m and r <= target:
        if (m-n)%3>0 and fractions.gcd(m,n)==1:
            r=0.5*q*m*n
            x+=int(target/r)
        n+=1
    m+=1    

n=1
while n < int((2.0*target*q-1)/3)+1:
    m,r=n+1,1
    while r <= target:
        if (m-n)%3>0 and fractions.gcd(m,n)==1:
            r=0.5*(m-n)*(2*n+m)/q
            x+=int(target/r)
        m+=1
    n+=1

print x