AtCoder Beginner Contest 165 D問題
D問題
難易度：茶色
必要となるのは以下の数式。
最大となるLの値を求める必要がある。
しかし1≤N≤10**12より全て計算すると間違いなくTLE。
工夫する必要がある。
L1 = Floor(A*N/B) L2 = Floor(N/B)*A L = L1 - L2
とりあえず周期性が知りたいので以下のようなスクリプトを書いてみた。
import math A,B,N = map(int,input().split()) #test lis = range(1,N) for x in lis: L1 = math.floor(A*x/B) L2 = math.floor(x/B)*A L = L1-L2 print('%d %d, %d, %d'%(x,L1,L2,L))
一応Xまで実行してみるとこんな感じ。
5 7 4 X L1, L2, L 1 0, 0, 0 2 1, 0, 1 3 2, 0, 2⬅︎最大 4 2, 0, 2
11 10 9 X L1, L2, L 1 1, 0, 1 2 2, 0, 2 3 3, 0, 3 4 4, 0, 4 5 5, 0, 5 6 6, 0, 6 7 7, 0, 7 8 8, 0, 8 9 9, 0, 9⬅︎最大
これでは周期性がいまいち分からないので、2つ目の例をもう少し検証。
11 10 9 X L1, L2, L 1 1, 0, 1 2 2, 0, 2 3 3, 0, 3 4 4, 0, 4 5 5, 0, 5 6 6, 0, 6 7 7, 0, 7 8 8, 0, 8 9 9, 0, 9⬅︎最大 ---------- 10 11, 11, 0 11 12, 11, 1 12 13, 11, 2 13 14, 11, 3 14 15, 11, 4 15 16, 11, 5 16 17, 11, 6 17 18, 11, 7 18 19, 11, 8 19 20, 11, 9⬅︎最大 20 22, 22, 0 21 23, 22, 1
気づく周期性は以下の通り。
- L2はB(=7)つ目でA(=5)ずつ増加していく点である。
- Lは0≤L≤B-1の数字をひたすら繰り返している。
つまり、Lが最大値となるのはB-1である必要がある。
では必ずしもLが最大のxは B-1なのか？
x = B-1
というわけでない。
なぜなら・・・1つ目の例で検証。
5 7 4 X L1, L2, L 1 0, 0, 0 2 1, 0, 1 3 2, 0, 2⬅︎最大(X=4の場合ここが答え) 4 2, 0, 2⬅︎最大(X=4の場合ここが答え) ---------- 5 3, 0, 3 6 4, 0, 4⬅︎最大(永遠に続く場合ここが答え) 7 5, 5, 0 8 5, 5, 0 9 6, 5, 1 10 7, 5, 2 11 7, 5, 2
上記の場合、Lの最大は4であるが、
X=Nまで達しない場合も考慮する必要がある。
いわゆるLが最大となる場合は、
- x = B-1 の場合
- x = Nの場合(もしくはその手前も含めて)
よってコードは以下の通りである。
import math A,B,N = map(int,input().split()) #Lが最大となるxは x = min(N, B-1) #最大値Lは print(math.floor(A*x/B) - math.floor(x/B)*A)
