kotonoha_pcg@気ままに雑記

kotonoha_pcgが気分次第で様々書き置きます.dlang関係他:http://kotonoha-pcg.hatenadiary.com

GCD and LCM

 先月,友人が「最大公約数と最大公倍数ってどう組めばいいんだ?」と聞いてきたので,適当にGCDはmod nして,LCMはそれから導き出せる(但し式は立てられない)と返しておいたのだが,先週AOJを解いててかなり序盤に出題されていた.それで,「あっ,この問題の事いってたのか」となったので書いておく.

理屈

 詳しいところは蟻本でも見てもらうことにして,理屈から説明する.GCDを求める→GCDの結果からLCMが求められる,といったところ.GCDそのものは簡単で,二数m,nが与えられた時,n!=0でありnがm未満であれば,関数にnとm%nを返す,ということ.コードだと,

int gcd(int m, int n){
	if(n==0){
		return m;
	}else{
		return gcd(n, m%n);
	}
}

となる.LCMの方は,ネットで他のサイトから拾ってきたので適当にくっつけて使用した.

AOJ #0005 GCD and LCM

  • 問題概要:20億以下の正の整数 a, b を入力したとき,a と b の最大公約数と最小公倍数を出力して終了するプログラムを作成する.

○注:a,bをm,nに置き換えている.

#include <iostream>
using namespace std;

int gcd( int m, int n )
{
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}

int lcm( int m, int n )
{
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	// lcm = m * n / gcd(m,n)
	return ((m / gcd(m, n)) * n); 
}

int main() {
	int m,n,s,d;
	while(cin>>m>>n){
		s=gcd(m,n);
		d=lcm(m,n);
		cout<<s<<" "<<d<<endl;
	}
	return 0;
}
  • sample input:8 6 50000000 30000000
  • sample output:2 24 10000000 150000000

LCMの式がどうたらは,跡で書くかもしれない(書くとは言っていない).書きました.