NYOJ-40公約数と公倍数
1000 ワード
公約数と公倍数
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
1
説明
明ちゃんは一つの問題に困っているので、今助けが必要です.問題は、2つの正の整数を与え、それらの最大公約数と最小公倍数を求めることです.
入力
1行目には、n組のテストデータがあることを示す整数n(0その後のn行には、2つの整数i,j(0しゅつりょく
各テストデータの最大公約数と最小公倍数を出力
サンプル入力
サンプル出力
ソース
[苗棟棟]オリジナル
アップロード者
苗棟
考え方:
最大公約数:転がり相除去法(ユークリッドアルゴリズム)gcd(a,b)=gcd(b,a mod b);
最小公倍数:最大公約数を求める後、式、a*b/iで求めることができる.
コード:
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
1
説明
明ちゃんは一つの問題に困っているので、今助けが必要です.問題は、2つの正の整数を与え、それらの最大公約数と最小公倍数を求めることです.
入力
1行目には、n組のテストデータがあることを示す整数n(0
各テストデータの最大公約数と最小公倍数を出力
サンプル入力
3
6 6
12 11
33 22
サンプル出力
6 6
1 132
11 66ソース
[苗棟棟]オリジナル
アップロード者
苗棟
考え方:
最大公約数:転がり相除去法(ユークリッドアルゴリズム)gcd(a,b)=gcd(b,a mod b);
最小公倍数:最大公約数を求める後、式、a*b/iで求めることができる.
コード:
#include <stdio.h>
int main()
{
int n;
scanf("%d", &n);
while(n --){
int a, b;
scanf("%d%d", &a, &b);
if(b > a){
int temp = a;
a = b;
b = temp;
}
int s = a * b;
while(1){
int ys = a % b;
if(!ys){
printf("%d %d
", b, s / b);
break;
}
a = b;
b = ys;
}
}
return 0;
}