最適化のために最大公約数を求める必要があって、 ユークリッド互除法と拡張ユークリッド互除法を書いたので、チラ裏に残しておく*1。 ユークリッド互除法 まずはよく見る実装をC#で public static int Gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; } 実にありがちな実装なのですが、どう見てもダサすぎ。 これってつまり、こういうことだよね。 public static int GcdR(int a, int b) { if (b == 0) return a; return GcdR(b, a % b); } スッキリしました。 何を思ったか、久々にHaskellでも書いてみることに。 って、実はHaskellでは最初からgcd関数が定義されていたりする。 http://