Javaの解答例：学習記録：A27 - Calculate GCD , 競技プログラミングの鉄則 演習問題集

はじめに

競技プログラミングの鉄則　演習問題集の

問題のポイント

• ユークリッドの互除法を使うこと
• ユークリッドの互除法では大きい方を割り、余りを格納
• 終了条件がどっちかが０になる。＝両方が0でない。と同じ意味。

目次

問題と解説

問題

atcoder.jp

解説

github.com

解答例

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();

        System.out.println(GCD(a, b));
// 下記に関数を作って、そこで最大公約数を出しています！
    }

    private static int GCD(int x, int y) {
        int tempX = x;
        int tempY = y;
// 領邦とも0以上、どっちかが0になったらやめてほしいからこう書いています。
        while (tempX > 0 && tempY > 0) {
            if (tempX > tempY) {
                tempX %= tempY;
            } else {
                tempY %= tempX;
            }
        }
        

        if (tempX == 0) {
            return tempY;
        } else {
            return tempX;
        }
    }
}

ちなみに公式の解答例

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 入力
        int A = sc.nextInt();
        int B = sc.nextInt();

        // 出力
        System.out.println(GCD(A, B));
    }

    // 正の整数 A と B の最大公約数を返す関数
    // GCD は Greatest Common Divisor（最大公約数）の略
    static int GCD(int A, int B) {
        while (A >= 1 && B >= 1) {
            if (A >= B) {
                A %= B; // A の値を変更する場合
            }
            else {
                B %= A; // B の値を変更する場合
            }
        }
        if (A >= 1) {
            return A;
        }
        return B;
    }
};