A - Required Remainder

cpcodeforcesdiv3math

最終更新日 2021年8月24日

問題

https://codeforces.com/contest/1374/problem/A (新しいタブで開く)

問題文

$x, y, n$ が与えられる。 $0 \le k \le n$ となる $k$ であって、 $k \bmod x = y$ となる最大値は？

制約

$1 \le t \le 5 \times 10^4$
$2 \le x \le 10^9$
$0 \le y < x$
$y \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

考察

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

式変形すると、 $a \le \frac{n - y}{x}$ になるので、 $a = \lfloor \frac{n-y}{x} \rfloor$ にして、 $k = 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;
}