ARC011 A問題 : 鉛筆リサイクルの新技術

問題. 鉛筆リサイクルの新技術

$m$ 本の使用済みの鉛筆から新たに $n$ 本の鉛筆が作り出される．初めに $N$ 本あるときに合計で何本の鉛筆を販売することができるか求めよ．

制約： $1 \le n < m < N \le 1,000$ （ $\, m$ と $n$ は互いに素）

解法．シミュレーション

$i$ 回目に手元にある新しい鉛筆の本数を $x_i$ とする．初期値を $x_0 = N$ として，
　　 $x_i = \lfloor \frac{x_{i - 1}}{m} \rfloor \times n + (x_{i - 1} \bmod m)$
を行い， $x_i$ が正の限りシュミレーションを繰り返す． $0 < i$ 回目で販売することのできる鉛筆の本数は $\lfloor \frac{x_{i - 1}}{m} \rfloor \times n$ なので，1回目以降で販売することができる鉛筆の本数の総和に $N$ を足した値が答えとなる．

販売回数は高々 $N$ となる．なぜならば， $x_i = a_i m + b_i$ としたとき，
　 $x_i = \lfloor \frac{x_{i - 1}}{m} \rfloor \times n + (x_{i - 1} \bmod m) = a_{i - 1} n + b_{i - 1} < a_{i - 1} m + b_{i - 1} = x_{i - 1}$
から $x_i < x_{i - 1}$ となるので，1回販売を行うたびに少なくとも1つ在庫が減る．したがって， $x_0 = N$ なので $O(N)$ 時間で答えが求まる．

計算時間： $O(N)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int m, n, N;
    cin >> m >> n >> N;

    int x = N, sum = N;
    while (m <= x) {
        sum += (x / m) * n;
        x = (x / m) * n + (x % m);
    }

    cout << sum << endl;

    return 0;
}

$n$ と $m$ が互いに素であることがどのように効いてくるのかがよく分からない．解説もないので誰か教えて欲しい・・・．