yukicoder yukicoder April Fool Contest 2019 O - ほぼ直角二等辺三角形 解説2
問題 → https://yukicoder.me/problems/no/3054
https://259-momone.hatenablog.com/entry/2019/04/02/002241 とは違う解法で解いたので書き残しておきます
問題
a²+(a+1)²=c² を変形して (2a+1)²+1=2c²
A=2a+1 とかで置くと A²+1=2c²
2=(A²+1)/c²
√2=√(A²+1)/c≒A/c
√2を2つの整数 (ただしAは奇数) で A/c と近似すればできそう
wikipediaで√2の項目を見ると「連分数展開を途中で止めると近似できる」と書いてある
有限回の連分数展開は再帰をするとできるので、1回だけ展開したのから60回くらいまで展開したのまでとりあえず計算した
出てきた分数が A²+1=2c²を満たすか確認→展開1回の値3/2以外は全部満たした！！！(未証明)
見た感じ1桁から18桁まで揃ってそうだし、cがX桁のものを出力するようにして投げたら通った
