結果

問題 No.1101 鼻水
コンテスト
ユーザー obakyan
提出日時 2022-04-29 17:02:41
言語 Lua
(LuaJit 2.1.1734355927)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,010 bytes
コンパイル時間 64 ms
コンパイル使用メモリ 5,376 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-28 22:52:45
合計ジャッジ時間 918 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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