最大公約数、最小公倍数、GCD and LCM(AOJ No.0005)

参考になりそうなページ

最大公約数(GCD;Greatest Common Divisor)

2つ以上の整数 $a_1, a_2, \cdots , a_n$ の最大公約数は $a_1, a_2, \cdots , a_n$ の最大の公約数

Euclidの互除法(Euclidean algorithm, Euclid's algorithm)

$a,b$ $(a\geq b)$ について、 ${ gcd(a,b) = gcd(b,a\% b) }$ が成立することを利用し最大公約数を求める方法。
※a

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

最小公倍数(LCM;Least Common Multiple)

2つ以上の整数 $a_1, a_2, \cdots , a_n$ の最小公倍数は $a_1, a_2, \cdots , a_n$ の最小の公倍数
二つの正整数 $a,b$ については、
$gcd(a,b)\bullet lcm(a,b) = ab \rightarrow lcm(a,b) = \frac{ab}{gcd(a,b)}$
が成り立つが、一般に3つ以上の正整数については成り立たない。

public static final int LCM(int a, int b){ return a / GCD(a, b) * b; }

2つ以上の整数のgcd,lcm

次のように再帰的に書ける
$gcd(a_1 , a_2 , \cdots ,a_n ) = gcd(gcd(a_1 , a_2 , \cdots , a_{n-1}) , a_n )$
$lcm(a_1 , a_2 , \cdots ,a_n ) = lcm(lcm(a_1 , a_2 , \cdots , a_{n-1}) , a_n )$

public static final int GCD(int[] x){
	int ret = x[0];
	for(int i = 1; i < x.length; ++i) ret = GCD(ret, x[i]);
	return ret;
}
public static final int LCM(int[] x){
	int ret = x[0];
	for(int i = 1; i < x.length; ++i) ret = LCM(ret, x[i]);
	return ret;
}

拡張ユークリッドの互除法(Extended Euclid's algorithm)

$ax+by = gcd(a, b)$ (Bézoutの等式; Bézout's identity - Wikipedia, the free encyclopedia)の整数解(x,y)は常に存在し、ユークリッドの互除法を拡張することで求められる。
$bx' + (a$ $\rm{mod}$ $b) y' = gcd(a,b)$
$bx' + (a - \lfloor a / b \rfloor b )y' = gcd(a,b)$
$ay' + b(x' - \lfloor a / b \rfloor y' ) = gcd(a,b)$
$b = 0$ のとき、 $a \times 1 + b \times 0 = a = gcd(a,b)$

//基本データ型の参照が使える言語ならこんな感じ(C++)
int extgcd(int a, int b, int& x, int& y){
	int res = a;
	x = 1;
	y = 0;
	if (b != 0){
		res = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
		// int x_, y_; res = extgcd(b, a%b, x_, y_); x = y_; y = x_ - (a / b) * y_;
	}
	return res;
}

javaではプリミティブ型の参照ができないので配列に入れた。swap関数は適当に作っとく。

/**
 * Calculates GCD(a,b) and a solution (x1,x2) for ax1 + bx2 = GCD(a,b) via Extended Euclid's algorithm. <br>
 * O(log max(a,b))
 * @param a
 * @param b
 * @return array {x1, x2, GCD(a,b)}
 */
public static int[] extGCD(int a, int b){
	int[] ret = new int[3];
	ret[2] = extGCD(a, b, ret);
	return ret;
}
/**
 * Calculates GCD(a,b) and a solution (x1,x2) for ax1 + bx2 = GCD(a,b) via Extended Euclid's algorithm. <br>
 * O(log max(a,b))
 * @param a
 * @param b
 * @param x	array(size>=2)←{x1, x2} |modify|
 * @return	GCD(a,b)
 */
public static int extGCD(int a, int b, int x[]){
	int g = a;
	x[0] = 1; x[1] = 0;
	if (b != 0){
		g = extGCD(b, a % b, x);
		swap(x, 0, 1);
		x[1] -= (a / b) * x[0];
	}
	return g;
}

GCD and LCM(AOJ No.0005)

lcmの計算をa / gcd(a,b) * bとして先に割っとかないとオーバーフローする(aはgcd(a,b)で割り切れるので先に割っておｋ)

import java.util.*;
public class aoj0005 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while( stdin.hasNext() ){
			int a = stdin.nextInt();
			int b = stdin.nextInt();
			System.out.println( GCD(a,b) + " " + LCM(a,b) );
		}
	}
	public static final int GCD(int a, int b){ return b == 0 ? a : GCD(b, a%b); }
	public static final int LCM(int a, int b){ return a / GCD(a, b) * b; } // a * b / gcd(a,b) だとoverflowした
}

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai