#author("2017-10-11T20:33:20+09:00","default:nobuoki","nobuoki") * 問題(和訳) [#v580c44a] Problem 75 「1通りの整数直角三角形」 https://goo.gl/bQ9FGg * 回答 [#p4fc38c0] 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}' * 実行結果 [#ma47c6e0] #pre{{ answer: 161667 real 0m8.442s user 0m8.710s sys 0m0.160s }} * 解説 [#n29c23ec] 原始ピタゴラス数を求め、その倍数含めいくつあるかを計算する 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 となる #prism(bash){{{{ #!/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}' }}}}