結果

問題 No.1101 鼻水
ユーザー 👑 obakyanobakyan
提出日時 2022-04-29 17:02:41
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,010 bytes
コンパイル時間 474 ms
コンパイル使用メモリ 7,196 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-11 08:19:26
合計ジャッジ時間 1,700 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,384 KB
testcase_07 AC 1 ms
4,384 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,384 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

local mfl, mce = math.floor, math.ceil
local function bezout_eq(a, b)
  if b == 0 then
    return 1, 0
  end
  local y, x = bezout_eq(b, a % b)
  y = y - mfl(a / b) * x
  return x, y
end

local function getgcd(x, y)
  while 0 < x do
    x, y = y % x, x
  end
  return y
end

local v, t, p = io.read("*n", "*n", "*n")
-- v = 1LL * v
-- t = 1LL * t
-- p = 1LL * p
if false and getgcd(v, t - 1) == 1 then
  -- v * b + (t - 1) * a = 1
  local b, a = bezout_eq(v, t - 1)
  while b < 0 or 0 <= a do
    b = b + t - 1
    a = a - v
  end
  a = -a
  -- (t - 1) * a + 1 = v * b
  
else
  local lim = 1LL * v * (p + 1LL)
  local min = 1LL
  local max = lim * 3LL
  while 1LL < max - min do
    local mid = (min + max) / 2LL
    local red = (mid - 1LL) / (t * 1LL)
    if mid - red <= lim then
      min = mid
    else
      max = mid
    end
  end
  local ans = tostring(1LL + min):gsub("LL", "")
  print(ans)
end

--[[

1, 0, t, t-1, 2t-1, 2t-2, 3t-2, 3t-3


(T-1)k + 1 === 0 mod V
(T-1)a + 1 = Vb
Vb - (T-1)a = 1


]]
0