ABC165 D - Floor Function

問題: N以下の非負整数 xに対する floor(Ax/B) - A•floor(x/B) の最大値を求めてください。

input: A, B, N

  • 1<= A <= 106
  • 1<= B <= 1012
  • 1<= N <= 1012

解法

f:id:keroid0:20210223173538p:plain
よって x/B の少数部分を最大化することがf(x)の最大化であることがわかった。
x/Bを最大化するにはxにB-1を代入する。B-1がNより大きい場合はNを代入する。
つまりf(min(B-1, N))が答え。