[AtCoder] ABC 180 D – Takahashi Unevolved

2020年10月17日2020年12月12日

問題

方針

カコモンジムに通うことを操作1、AtCoder ジムに通うことを操作2とします。

\( i \) 回目の操作を行ったときの高橋君の強さを \( X_i \) とします。操作1を行うと、\( X_{i + 1} = AX_i \) となり、増分は

\[X_{i + 1} – X_{i} = (A – 1)X_i\]

となります。\( (A – 1)X_i > B \) のとき操作2を行った方が高橋君の強さは増えないことが分かります。したがって、\( (A – 1)X_i  \leq B \) を満たす限り、操作1を行い、残りは操作2を行います。

操作1を行った方が良い条件は、

\[ X_iA \leq Y – 1 \wedge (A – 1)X_i \leq B\]

なので、オーバーフローに注意する必要があります。128ビット整数を使うか、Python などの多倍長整数を気軽に扱える言語を使います。

コード

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

int main() {
    __int128_t X1, X2;
    ll x, y, a, b;
    cin >> x >> y >> a >> b;
    ll v = 0;
    while (true) {
        X1 = (__int128) x * (__int128) a;
        X2 = (__int128) x * (__int128) (a - 1);
        if (X1 <= y - 1 && X2 <= b) {
            v++;
            x = x * a;
        } else {
            break;
        }
    }
    ll t = (y - 1 - x) / b;
    v += t;
    cout << v << "\n";
    return 0;
}