AtCoder茶色解く４

今回解くのはこちら
D - Floor Function

floor(t)は、実数t以下の最大の整数とのこと。
問題のイメージがつきづらいので、実際にいくつか例をもって計算してみます。
A=5, B=7, N=4のとき
Ax/B, x/Bの値は

x=1, l=floor(5/7)=0, m=floor(1/7)=0  l-5*m=0
x=2, l=floor(10/7)=1, m=floor(2/7)=0 l-5*m=1
x=3, l=floor(15/7)=2, m=floor(3/7)=0 l-5*m=2
x=4, l=floor(20/7)=2, m=floor(4/7)=0 l-5*m=2

Nが10**12なので、通常のfor文では実行時間が間に合わないと判断、
nの数を減らせる工夫を考えます。

ここで、xが7の倍数になるとき、mの値が増加します。
それに合わせて、計算式も単調増加から一時的に減少に転じます。
よって、最大値を求めるとしたらxが7の倍数-1, 7の倍数のとき、およびNに一致したときと考えます。

例えばN=15だとすると、
x=6, 7, 13, 14, 15について計算ができればいいと思われます。

この場合は、

i = N//7 # 2になる
for x in range(i):
  x1 = x*7-1
  x2 = x*7
xn = N

となるはず。

...
と思ったのですが、ちょっとうまくいかなかったので参考資料をたよりに再確認
AtCoder ABC 165 D - Floor Function (400 点) - けんちょんの競プロ精進記録

周期性を見るためにもう一度手計算してみると。。。。

x=1, l=floor(5/7)=0, m=floor(1/7)=0  l-5*m=0
x=2, l=floor(10/7)=1, m=floor(2/7)=0 l-5*m=1
x=6, l=floor(30/7)=2, m=floor(6/7)=0 l-5*m=2
x=7, l=floor(35/7)=2, m=floor(7/7)=0 l-5*m=0
x=13, l=floor(65/7)=2, m=floor(13/7)=0 l-5*m=2
x=14, l=floor(70/7)=2, m=floor(14/7)=0 l-5*m=0

たしかに周期性があるため、この例でいえばx=1~6 (B-1)までで試せばよい。
また、その数は増えていくのだから、
NがB-1を超えた場合はB-1の値、NがB-1以下であればxの最大値で計算すればよい。

A, B, N = map(int, input().split())

min = N
if N > B-1:
  min = B-1
print(A*min//B - A*(min//B))

ということで、完成。
一見不思議な形の数式については、具体的な値を入れて法則を見出すことにする。
今回も、きちんと出力値を出していれば答えの周期自体に気づけたはず・・・精進します。