AOJ 3052 Milk (RUPC 2019 day2-B)

難しかった

問題へのリンク

問題概要

ちょうど 本の牛乳の空き瓶を持っていくと新たに 本の牛乳の入った瓶と交換できる。

最初に 本の牛乳の入った瓶を持っているとき、最大で何本分の牛乳を飲めるかを 1000000007 で割ったあまりを求めよ。

制約

• 
• <
• 

考えたこと

最初は 本あったら、そのうち 本ずつのペアを 個作れて、、、という風に考えていたが、この方向でのシミュレションは TLE するので注意が必要となる。

残っている牛乳本数が であるとき、 であるならば、

• のうちの 本を 本の牛乳入り瓶と交換できて、このとき は になる

という風に理解すればよい。この操作の回数を とすると交換によって 本の牛乳を飲むことができることになる (これにプラスして最初の 本がある)。

を求めたい。

• のとき
• のとき
• ...
• のとき
• ...

であることを思うと、 で求められる。

#include <iostream>
using namespace std;

const long long MOD = 1000000007;
int main() {
    long long a, b, x;
    cin >> a >> b >> x;

    long long N = max(0LL, (x - b) / (a - b));
    x %= MOD;
    N %= MOD;
    b %= MOD;
    cout << (x + N * b) % MOD << endl;
}