最大公約数 (GCD)

2つの整数 a と b の最大公約数（GCD）とは、両方を割り切ることができる最大の整数を指します。記号では gcd(a, b) と表されます。

例えば、gcd(15, 18) と gcd(-15, -18) はどちらも 3 になります。

ユークリッドの互除法

最大公約数を求める代表的な方法として、ユークリッドの互除法が知られています。

このアルゴリズムの仕組み：

• 大きい数を小さい数で割り、余りを求めます。
• 次に、小さい数と余りを使って再び割り算を行い、余りが 0 になるまで繰り返します。
• 余りが 0 になったときの除数が、最大公約数です。

例として、1997 と 615 の最大公約数を求めてみます：

1997 ÷ 615 = 3 ... 152
615 ÷ 152 = 4 ... 7
152 ÷ 7 = 21 ... 5
7 ÷ 5 = 1 ... 2
5 ÷ 2 = 2 ... 1
2 ÷ 1 = 2 ... 0

最大公約数は 1 です。

コード例（Java）

public static int gcd(int a, int b) {
    return (b != 0) ? gcd(b, a % b) : a;
}

最小公倍数 (LCM)

2つの整数 a と b の最小公倍数（LCM）は、a と b の両方で割り切れる最小の正の整数です。

最大公約数と最小公倍数の関係：
gcd(a, b) × lcm(a, b) = a × b

コード例（Java）

public static int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

応用例1：薬品の投与量を最適化する問題

ある容器に薬品を追加する際、容量 n と m にちょうど満たす最大の単位量 p を求めます。

条件：
n + m が p で割り切れること。
p はできるだけ大きくすること。

ソースコード

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            sc.nextLine(); // 改行を消費
            int p = gcd(n, m);
            System.out.println(p);
        }
    }

    public static int gcd(int a, int b) {
        return (b != 0) ? gcd(b, a % b) : a;
    }
}

応用例2：最大公約数と最小公倍数を求める

入力された2つの整数から、最大公約数と最小公倍数を出力します。

コード例

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        System.out.print(gcd(a, b) + " " + lcm(a, b));
    }

    public static int gcd(int a, int b) {
        return (b != 0) ? gcd(b, a % b) : a;
    }

    public static int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }
}

応用例3：分母40の既約分数を列挙する

分母が 40 で、分子が 40 より小さい既約分数をすべて列挙します。

コード例

public class Main {
    public static void main(String[] args) {
        for (int i = 1; i < 40; i++) {
            if (gcd(i, 40) == 1) {
                System.out.print(i + "/40,");
            }
        }
    }

    public static int gcd(int a, int b) {
        return (b != 0) ? gcd(b, a % b) : a;
    }
}