ユークリッドの互除法（2題）

C++ 競技プログラミング

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
この本（通称：蟻本）の章末で紹介されている練習問題をひたすらといている。

今回はユークリッドの互除法。最近はユークリッドの互除法は高校の数学でも習うようで、認知度が高い。練習問題は3題紹介されていたが、そのうちの1題（POJ2429）はかなり難しいので他の人の解答を丸写しして AC をゲットした（意味ない）。

AOJ0005 GCD and LCM

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0005&lang=jp
ふつうにユークリッドの互除法の練習。

#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

int main() {
  ifstream cin("../test.txt");
  int a, b, g;
  long long l;
  while (cin >> a >> b) {
    g = gcd(a, b);
    l = a / g * b / g * g;
    cout << g << " " << l << endl;
  }
}

POJ2429: GCD & LCM Inverse

2429 -- GCD & LCM Inverse

問題概要

ある2つの自然数 a, b の最大公約数 GCD と最小公倍数 LCM が与えられるので、もとの a と b のうち、a + b が最小になる組を求める。

解法

高速な素数判定と素因数分解のアルゴリズムを知らないと解けない。
こうやって解いている人がいた。
POJ 2429 - GCD & LCM Inverse - fuqinho@競技プログラミング
Java だとこうやって解いている人がいる。
ACM and java--GCD & LCM Inverse(poj2429)
けど、これと同じ実装を C++ で真似しても、 TLE になった。何が違うんだろう。Java の方が速いのか？

POJ:1930 Dead Fraction

1930 -- Dead Fraction

問題概要

与えられた循環小数を既約分数に直す。ただし、どこから巡回しているかはわからない。既約分数に直したときに、分母がもっとも小さくなる分数を出力する。

解法

約分なので、分母と分子を最大公約数で割ればよい。

#include <fstream>
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
const int INF = 1000000000;

// a, b の最大公約数
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

int main() {
  while (true) {
    // 入力
    char c[30];
    cin >> c;
    string s(c);
    if (s.length() == 1) break;
    // 数字部分を抜き出す
    int loc = s.find("...", 0);
    string digits = s.substr(2, loc - 2);
    int d = digits.length();
    int n = atoi(digits.c_str());
    // 循環する箇所についてループ
    int res_num = INF;
    int res_den = INF;
    for (int i = 1; i <= d; i++) {
      // 分数を作る
      int m = n / pow(10.0, i);
      int num = n - m;
      int den = (10 * pow(10.0, i - 1) - 1) * 10 * pow(10.0, d - i - 1);
      // 約分する
      int g = gcd(num, den);
      num /= g;
      den /= g;
      // 分母が小さければ結果を更新
      if (den < res_den) {
        res_den = den;
        res_num = num;
      }
    }
    // 出力
    cout << res_num << "/" << res_den << endl;
  }
}