CF Round #653 A - Required Remainder


Tags:cpcodeforcesdiv3math

問題

https://codeforces.com/contest/1374/problem/A

問題文

x,y,nx, y, n が与えられる。0kn0 \le k \le n となる kk であって、kmodx=yk \bmod x = y となる最大値は?

制約

  • 1t5×1041 \le t \le 5 \times 10^4
  • 2x1092 \le x \le 10^9
  • 0y<x0 \le y < x
  • yn109y \le n \le 10^9

サンプル

7
7 5 12345
5 0 4
10 5 15
17 8 54321
499999993 9 1000000000
10 5 187
2 0 999999999
12339
0
15
54306
999999995
185
999999998

考察

整理すると、 k=ax+yk = ax + y かつ knk \le n となる kk の最大値を求める問題。
これを満たすような整数 aa の最大値を求められればいい。

式変形すると、 anyxa \le \frac{n - y}{x} になるので、 a=nyxa = \lfloor \frac{n-y}{x} \rfloor にして、 k=ax+yk = ax + y を求めればいい。

コード

https://codeforces.com/contest/1374/submission/126804568

void solve() {
  ll x, y, n;
  cin >> x >> y >> n;
  ll a = (n - y) / x;
  ll ans = a * x + y;
  cout << ans << endl;
}