結果

問題 No.2183 LCA on Rational Tree
ユーザー tnakao0123
提出日時 2023-01-10 11:25:03
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 97 ms / 2,000 ms
コード長 2,649 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 671 ms
コンパイル使用メモリ 56,912 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-21 11:59:29
合計ジャッジ時間 1,589 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* -*- coding: utf-8 -*-
 *
 * 2183.cc:  No.2183 LCA on Rational Tree - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
 
using namespace std;

/* constant */

const int MAX_P = 35000;
const int INF = (1U << 31) - 1;

/* typedef */

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

struct Rat {
  int p, q;
  Rat() {}
  Rat(int _p, int _q): p(_p), q(_q) {}

  void read() { scanf("%d%d", &p, &q); }
  int d() const { return q - p; }

  bool operator==(const Rat r) const { return (ll)p * r.q == (ll)r.p * q; }
  bool operator!=(const Rat r) const { return (ll)p * r.q != (ll)r.p * q; }
  bool operator<(const Rat r) const { return (ll)p * r.q < (ll)r.p * q; }
  bool operator>(const Rat r) const { return (ll)p * r.q > (ll)r.p * q; }
};

/* global variables */

bool primes[MAX_P + 1];
vi pnums;

/* subroutines */

int gen_primes(int maxp, vi &pnums) {
  fill(primes, primes + maxp + 1, true);
  primes[0] = primes[1] = false;

  int p;
  for (p = 2; p * p <= maxp; p++)
    if (primes[p]) {
      pnums.push_back(p);
      for (int q = p * p; q <= maxp; q += p) primes[q] = false;
    }
  for (; p <= maxp; p++)
    if (primes[p]) pnums.push_back(p);
  return (int)pnums.size();
}

bool prime_decomp(int n, vi &pnums, vpii& pds) {
  pds.clear();

  int pn = pnums.size();
  for (int i = 0; i < pn; i++) {
    int pi = pnums[i];
    if (pi * pi > n) {
      if (n > 1) pds.push_back(pii(n, 1));
      return true;
    }

    if (n % pi == 0) {
      int fi = 0;
      while (n % pi == 0) n /= pi, fi++;
      pds.push_back(pii(pi, fi));
    }
  }
  return false;
}

template <typename T>
T gcd(T m, T n) {  // m >= 0, n >= 0
  if (m < n) swap(m, n);
  while (n > 0) {
    T r = m % n;
    m = n;
    n = r;
  }
  return m;
}

inline Rat reduce(Rat r) {
  int g = gcd(r.p, r.q);
  return Rat(r.p / g, r.q / g);
}

Rat forward(Rat r) {
  if (r.d() == 1) return r;

  vpii pds;
  prime_decomp(r.d(), pnums, pds);

  int minp = INF;
  for (auto pd: pds) {
    int pi = pd.first;
    minp = min(minp, (r.p / pi + 1) * pi);
  }

  return reduce(Rat(minp, r.q + (minp - r.p)));
}

/* main */

int main() {
  gen_primes(MAX_P, pnums);

  int tn;
  scanf("%d", &tn);

  while (tn--) {
    Rat u, v;
    u.read(), v.read();

    while (u != v) {
      while (u.d() != v.d()) {
	//printf("%d/%d %d/%d\n", u.p, u.q, v.p, v.q);
	if (u.d() > v.d()) u = forward(u);
	else v = forward(v);
      }

      if (u > v) swap(u, v);
      if (u.d() > 1) {
	Rat u1 = forward(u);
	u = min(u1, v);
      }
      else
	u = v;
    }

    printf("%d %d\n", u.p, u.q);
  }
  return 0;
}
0