けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 3052 Milk (RUPC 2019 day2-B)

難しかった

問題へのリンク

問題概要

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

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

制約

  •  1 \le a \le 10^{15}
  •  0 \le b <  a
  •  0 \le x \le 10^{15}

考えたこと

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

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

  •  x のうちの  a 本を  b 本の牛乳入り瓶と交換できて、このとき  x x - a + b になる

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

 N を求めたい。

  •  x = a のとき  N = 1
  •  x = a+1 のとき  N = 1
  • ...
  •  x = a + (a-b) のとき  N = 2
  • ...

であることを思うと、 N = (x-b) / (a-b) で求められる。

#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;
}