読者です 読者をやめる 読者になる 読者になる

ユークリッドの互除法(2題)

プログラミングコンテストチャレンジブック [第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;
  }
}