Problem 75 「1通りの整数直角三角形」
https://goo.gl/bQ9FGg
awk 'function gcd(p,q){if(q==0)return p;else return gcd(q,p%q)}BEGIN{for(n=1;n<866;n++)for(m=n+1;m<=866;m+=2)if(gcd(m,n)==1){L=2*m*m+2*m*n;for(i=1;i<=1500000/L;i++)print L*i}}' | awk '{a[$1]++}END{for(v in a)if(a[v]==1)b++;print "answer: "b}'
answer: 161667 real 0m8.442s user 0m8.710s sys 0m0.160s
原始ピタゴラス数を求め、その倍数含めいくつあるかを計算する
https://goo.gl/YFS4jD ピタゴラスの定理 - Wikipedia
自然数の組 (a, b, c) が原始ピタゴラス数であるためには、ある自然数 m, n が
* m と n は互いに素(m と n の最大公約数は 1) * m > n * m - n は奇数
を満たすとき、
(a, b, c) = (m^2 - n^2, 2mn, m^2 + n^2)
の関係がある
m, n の探索範囲は、
三角形の長さの和 = 2*m^2 + 2mn <= 1,500,000 なので、
n=1のときmは最大だから 2m(m+1) <= 1,500,000
したがって m <= sqrt(1,500,000/2) = 866 となる
#!/bin/sh
awk '
# 最大公約数を求める関数(ユークリッドの互除法)
function gcd(p,q){
if(q==0)
return p;
else
return gcd(q,p%q)
}BEGIN{
# 力技で探索
# n: 1 <= n <866
# m: n+1<= m <=866
for(n=1;n<866;n++)
for(m=n+1;m<=866;m+=2)
# 原始ピタゴラス数の条件: mとnは互いに素
if(gcd(m,n)==1){
# 以下、デバッグ用
#a=m^2-n^2;
#b=2*m*n;
#c=m^2+n^2;
# 長さを求める
L=2*m*m+2*m*n;
# 原始ピタゴラス数の整数倍を含め、Lを出力
for(i=1;i<=1500000/L;i++)
print L*i
# デバッグ用
#print L*i,m,n,a*i,b*i,c*i
}
}' |
# 1度しか現れないL(=$1)の数が答え
awk '{a[$1]++}END{for(v in a)if(a[v]==1)b++;print "answer: "b}'