ABC165 D - Floor Function

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import collections
import itertools

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def f(A, B, x):
    return math.floor(A * x / B) - A * math.floor(x / B)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, N = il()
    print(f(A, B, min(B - 1, N)))


if __name__ == '__main__':
    main()

考え方

条件式math.floor(A * x / B) - A * math.floor(x / B)を
math.floor(A * x / B)とA * math.floor(x / B)に分けて考える。

math.floor(A * x / B)はx = Bの場合に計算結果がAとなり、
x < Bの範囲(1 <= x <= B-1)では、単調増加となる。
また、xがBを上回る場合でも同様の増加で、
x = 2Bの時に、計算結果は2Aとなる。

A * math.floor(x / B)はx = Bの場合に計算結果がAとなり、
x < Bの範囲(1 <= x <= B-1)では、計算結果は0になる。
つまり、xがBの倍数の時に限り、値が変動し、
x = BのときA、x = 2Bのとき2Aとなる。

以上のことから、探索を行う範囲は、
1 <= x <= B-1のみでよい。
また、xはN以下という条件があるため、
結果が最大になるxはmin(N, B-1)になる。