AtCoder ABC 046 C - AtCoDeerくんと選挙速報 (ARC 062 C) (4Q, 水色, 300 点)

問題文の理解が大変かもしれない

• 問題へのリンク

問題概要（意訳）

2 つの正の整数 を次のように 回更新していく。最初、 である。

---

回目の更新では 2 つの互いに素な正の整数 が与えられるので、

• 
• 
• 

を満たすような 2 つの正の整数 を 1 つ求めて、 をそれぞれ に置き換える。

---

最終結果における の値の最小値を求めよ。

制約

• 
• 

考えたこと

単純に、毎回 の値をできるだけ小さく抑えるようにすればよい。そのためには

• 
• 

を満たすような最小の を求めて、次のようにすればよい。

• を の値に置き換える
• を の値に置き換える

毎回の処理は の計算量で実行できるので、全体の計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, T, A, res_t = 1, res_a = 1;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> T >> A;

        // Tx >= res_t, Ay >= res_a を満たす最小の x, y を求めて、その最大値をとる
        long long x = (res_t + T - 1) / T;
        long long y = (res_a + A - 1) / A;
        res_t = T * max(x, y), res_a = A * max(x, y);
    }
    cout << res_t + res_a << endl;
}