最適化のために最大公約数を求める必要があって、 ユークリッド互除法と拡張ユークリッド互除法を書いたので、チラ裏に残しておく*1。 ユークリッド互除法まずはよく見る実装をC#で public static int Gcd(int a, int b) { while (b != 0) { int r = a % b; …