本题和第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
|