結果
問題 | No.546 オンリー・ワン |
ユーザー | 👑 obakyan |
提出日時 | 2022-04-17 21:30:12 |
言語 | Lua (LuaJit 2.1.1696795921) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 1,892 bytes |
コンパイル時間 | 202 ms |
コンパイル使用メモリ | 6,816 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-08 00:01:02 |
合計ジャッジ時間 | 869 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 4 ms
5,376 KB |
testcase_09 | AC | 6 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
ソースコード
local mfl, mce = math.floor, math.ceil local bls, brs = bit.lshift, bit.rshift local bxor = bit.bxor local function getgcd(x, y) while 0 < x do x, y = y % x, x end return y end local function getlcm(x, y) local gcd = getgcd(x, y) return mfl(x / gcd) * y end local function grayCode(x) return bxor(x, brs(x, 1)) end local function grayWalk(size, add_func, rm_func, work_func) local prv = 0 local total = bls(1, size) - 1 local bpos = {} for i = 1, size do bpos[bls(1, i - 1)] = i end -- work_func() for i = 1, total do local v = grayCode(i) if prv < v then prv, v = v, v - prv add_func(bpos[v]) else prv, v = v, prv - v rm_func(bpos[v]) end work_func() end end local n, left, right = io.read("*n", "*n", "*n") local a = {} for i = 1, n do a[i] = io.read("*n") end local t = {} local f = {} local ai = 0 local gx = 0 local gc = 0 local gr = 0 local function add_func(idx) f[idx] = true gc = gc + 1 end local function rm_func(idx) f[idx] = false gc = gc - 1 end local function work_func() local v = false for i = 1, n - 1 do if f[i] then if v then v = getlcm(v, t[i]) else v = getlcm(ai, t[i]) end end if v and gx < v then return end end if gc % 2 == 1 then gr = gr - mfl(gx / v) else gr = gr + mfl(gx / v) end end local function solvesub(ai, x) grayWalk(n - 1, add_func, rm_func, work_func) end local function solve(x) gr = 0 gx = x gr = 0 for i = 1, n do local tc = 0 for j = 1, n do if i ~= j then tc = tc + 1 t[tc] = a[j] end end ai = a[i] for i = 1, n - 1 do f[i] = false end gc = 0 gr = gr + mfl(x / ai) grayWalk(n - 1, add_func, rm_func, work_func) end return gr end local ret = solve(right) if 1 < left then ret = ret - solve(left - 1) end print(ret)