If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.
{20,48,52}, {24,45,51}, {30,40,50}
For which value of p ≤ 1000, is the number of solutions maximised?
整数边长直角三角形
若三边长{a,b,c}均为整数的直角三角形周长为p,当p = 120时,恰好存在三个不同的解:
{20,48,52}, {24,45,51}, {30,40,50} 在所有的p ≤ 1000中,p取何值时有解的数目最多?
count = 0
v = 0
for p in range(3, 1001):
table = []
for a in range(1, p - 1):
for b in range(1, p - 1 - a):
c = p - a - b
if a + b > c and b + c > a and a + c > b:
result = [a, b, c]
result = sorted(result)
if not result in table and (result[0] * result[0] + result[1] * result[1] == result[2] * result[2]):
table.append(result)
if table:
if len(table) > count:
v = p
count = len(table)
print p, table
print v, count
上面是愚蠢的暴力破解方法,然后算出答案之后,我开始扮演事后诸葛亮了,blabla,先算出最小边长比,然后算最小公倍数1000以内的就行了,blabla(piapia打回自己的脸)
numbers = []
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
for c in range(1, 100):
for b in range(1, c + 1):
for a in range(1, b + 1):
if a * a + b * b == c * c and a + b >= c and b + c >= a and a + c >= b and gcd(a, b) == 1 and gcd(c, b) == 1 and gcd(a, c) == 1 :
numbers.append(a + b + c)
large = 0
r = 0
for i in range(1, 1001):
count = 0
for number in numbers:
if i % number == 0:
count += 1
if count > large:
large = count
r = i
print r