「牛の舌って薄いんですね」

(出典:蒼樹うめ『ひだまりスケッチ』6巻11ページ「一頭から一枚」3コマ目)

ふみをチャレンジ[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関数の中に放り込んである。