ふみをチャレンジ[6]
時間がない…とりあえず記事の作成だけ。
すっかり忘れてた。早く寝たいのに…
問題
0005: GCD and LCM - AIZU ONLINE JUDGE
結果から先に言うと、正解できてない。したがって以下は不正解の答案を載せてある。
答案
C
#include <stdio.h> long gcd(long, long); long lcm(long, long); int main() { long a, b; while(~scanf("%ld %ld", &a, &b)) { printf("%ld %ld\n", gcd(a, b), lcm(a, b)); } return 0; } long gcd(long m, long n) { long r; while(n) { r = m % n; m = n; n = r; } return m; } long lcm(long m, long n) { return m * n / gcd(m, n); }
反省
ユークリッドの互除法を用いてコードを書いてみたが、結果はWrong Answer。intをlongに換えてみたりしたけど、何が問題なのかよく分からない…今日は早く寝たいので明日また考えることにする。
[追記] (2012-01-13)
もう一度、挑戦した。
#include <stdio.h> int main() { long long unsigned int a, b, m, n, r, gcd, lcm; while(~scanf("%llu %llu", &a, &b)) { m = a; n = b; while(n) { r = m % n; m = n; n = r; } gcd = m; lcm = a * b / gcd; printf("%llu %llu\n", gcd, lcm); } return 0; }
long型にしてたのをlong long unsigned int型に換えたらうまくいった。あと、LCM求めるときにGCDを再度求めてるのが気に食わなかったので、全部をmain関数の中に放り込んである。