Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
ある長さの鉄線を折り曲げて$3$辺の長さが整数の直角三角形を作るとき, その方法が$1$通りしかないような最短の鉄線の長さは$12$cmである. 他にも沢山の例が挙げられる.
$12 cm: (3,4,5)$
$24 cm: (6,8,10)$
$30 cm: (5,12,13)$
$36 cm: (9,12,15)$
$40 cm: (8,15,17)$
$48 cm: (12,16,20)$
それとは対照的に, ある長さの鉄線 (例えば$20cm$) は$3$辺の長さが整数の直角三角形に折り曲げることができない. また$2$つ以上の折り曲げ方があるものもある. $2$つ以上ある例としては, $120cm$の長さの鉄線を用いた場合で, $3$通りの折り曲げ方がある.
$120 cm: (30,40,50), (20,48,52), (24,45,51)$
$L$を鉄線の長さとする. 直角三角形を作るときに$1$通りの折り曲げ方しか存在しないような $L ≤ 1,500,000$ の総数を答えよ.
注: この問題は最近変更されました. あなたが正しいパラメータを使っているか確認してください.
アプローチ
引用元：ピタゴラス数
$a^2+b^2=c^2$を満たすような整数$a$、$b$、$c$を考える。
もろもろの考察により下記を全て満たす整数$m$、$n$を考えればよい。
0<n<m \\
(a,b,c)=(m^2-n^2,2mn,m^2+n^2) \\
gcd(m,n)=1 \\
(m-n)\%2=1
以上より$(a,b,c)=(3,4,5)$は求まるが$(a,b,c)=(30,40,50)$のようなある組み合わせを定数倍したものは求めることができない。
そこで、最初に基礎となる組み合わせを求め、そこに長さが$150$万を超えない範囲で定数倍をする。
解答
time seq 999 |
awk '{for(i=1;i<$1;i++){if(($1-i)%2==1){print $1,i}}}' |
awk '{a=$1;b=$2;r=a%b;while(r!=0){a=b;b=r;r=a%b};if(b==1){print}}' |
awk '{a=$1^2-$2^2;b=2*$1*$2;c=$1^2+$2^2;print a,b,c,a+b+c}' |
awk '{k=1;while($4*k<=1500000){print $1*k,$2*k,$3*k,$4*k;k++}}' |
sort -k4,4n |
uniq -f3 -c |
awk '$1==1' |
wc -l
161667
real 0m12.817s
user 0m15.844s
sys 0m0.532s
最初はもう少し緩い条件でやれば最初から全量が求まるのではと思っていたが、どうにも$(a,b,c)=(30,40,50)$のような求められない組み合わせが出てきてしまい、答えが違ってしまっていた。
そこで上記のようなやり方にシフトしたところ、すぐに解答にいきつくことができた。