AOJ0005 GCD and LCM

問題

GCD and LCM | Aizu Online Judge

コメント

最大公約数(gcd)はユークリッドの互除法を使って求める。最小公倍数(lcm)は最大公約数を使って求めることできる。
入力は20億以下だからint型を使用することはできるが、lcmの計算をすると20億を超えるのでlong型を使うほうが安全、という考え。

ソース

import java.util.Scanner;

public class Main {
	public void run() {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			long a = sc.nextInt();
			long b = sc.nextInt();
			long c = gcd(a, b);
			// 最小公倍数
			long d = a * b / c;
			System.out.println(c + " " + d);
		}
		sc.close();
	}

	// 最大公約数
	// ユークリッドの互除法
	public long gcd(long a, long b) {
		if (b == 0) {
			return a;
		}
		else {
			return gcd(b, a % b);
		}
	}
	public static void main(String[] args) {
		new Main().run();
	}

• メモ

lcmがgcdを使って解くことができる証明(合ってるかは謎)
式　lcm = a * b / gcd(a, b)
(証明)
gcd(a, b) = mとおく。
(右辺) = lcm = (a / m) * (b / m) * m = a * b / (m / m) * m
= a * b / m = a * b / gcd(a, b) = (左辺)
よって、
lcm = a * b / gcd(a, b)
(証明終わり)