結果
| 問題 |
No.2526 Kth Not-divisible Number
|
| コンテスト | |
| ユーザー |
 mattu34
|
| 提出日時 | 2023-11-04 15:13:38 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 35,892 bytes |
| コンパイル時間 | 321 ms |
| コンパイル使用メモリ | 82,048 KB |
| 実行使用メモリ | 99,456 KB |
| 最終ジャッジ日時 | 2024-09-25 22:04:59 |
| 合計ジャッジ時間 | 22,744 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 2 TLE * 9 |
ソースコード
import sys
input = lambda: sys.stdin.readline().strip()
from functools import lru_cache
import math
from collections import *
from fractions import Fraction
import heapq
import bisect
import itertools
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
# sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
# input = lambda:sys.stdin.readline().rstrip("\r\n")
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar("T")
class SortedMultiset(Generic[T]):
BUCKET_RATIO = 50
REBUILD_RATIO = 170
def _build(self, a=None) -> None:
"Evenly divide `a` into buckets."
if a is None:
a = list(self)
size = self.size = len(a)
bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
self.a = [
a[size * i // bucket_size : size * (i + 1) // bucket_size]
for i in range(bucket_size)
]
def __init__(self, a: Iterable[T] = []) -> None:
"Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
a = list(a)
if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):
a = sorted(a)
self._build(a)
def __iter__(self) -> Iterator[T]:
for i in self.a:
for j in i:
yield j
def __reversed__(self) -> Iterator[T]:
for i in reversed(self.a):
for j in reversed(i):
yield j
def __len__(self) -> int:
return self.size
def __repr__(self) -> str:
return "SortedMultiset" + str(self.a)
def __str__(self) -> str:
s = str(list(self))
return "{" + s[1 : len(s) - 1] + "}"
def _find_bucket(self, x: T) -> List[T]:
"Find the bucket which should contain x. self must not be empty."
for a in self.a:
if x <= a[-1]:
return a
return a
def __contains__(self, x: T) -> bool:
if self.size == 0:
return False
a = self._find_bucket(x)
i = bisect_left(a, x)
return i != len(a) and a[i] == x
def count(self, x: T) -> int:
"Count the number of x."
return self.index_right(x) - self.index(x)
def add(self, x: T) -> None:
"Add an element. / O(√N)"
if self.size == 0:
self.a = [[x]]
self.size = 1
return
a = self._find_bucket(x)
insort(a, x)
self.size += 1
if len(a) > len(self.a) * self.REBUILD_RATIO:
self._build()
def discard(self, x: T) -> bool:
"Remove an element and return True if removed. / O(√N)"
if self.size == 0:
return False
a = self._find_bucket(x)
i = bisect_left(a, x)
if i == len(a) or a[i] != x:
return False
a.pop(i)
self.size -= 1
if len(a) == 0:
self._build()
return True
def lt(self, x: T) -> Union[T, None]:
"Find the largest element < x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] < x:
return a[bisect_left(a, x) - 1]
def le(self, x: T) -> Union[T, None]:
"Find the largest element <= x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] <= x:
return a[bisect_right(a, x) - 1]
def gt(self, x: T) -> Union[T, None]:
"Find the smallest element > x, or None if it doesn't exist."
for a in self.a:
if a[-1] > x:
return a[bisect_right(a, x)]
def ge(self, x: T) -> Union[T, None]:
"Find the smallest element >= x, or None if it doesn't exist."
for a in self.a:
if a[-1] >= x:
return a[bisect_left(a, x)]
def __getitem__(self, x: int) -> T:
"Return the x-th element, or IndexError if it doesn't exist."
if x < 0:
x += self.size
if x < 0:
raise IndexError
for a in self.a:
if x < len(a):
return a[x]
x -= len(a)
raise IndexError
def index(self, x: T) -> int:
"Count the number of elements < x."
ans = 0
for a in self.a:
if a[-1] >= x:
return ans + bisect_left(a, x)
ans += len(a)
return ans
def index_right(self, x: T) -> int:
"Count the number of elements <= x."
ans = 0
for a in self.a:
if a[-1] > x:
return ans + bisect_right(a, x)
ans += len(a)
return ans
import math
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar("T")
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py
class SortedSet(Generic[T]):
BUCKET_RATIO = 50
REBUILD_RATIO = 170
def _build(self, a=None) -> None:
"Evenly divide `a` into buckets."
if a is None:
a = list(self)
size = self.size = len(a)
bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
self.a = [
a[size * i // bucket_size : size * (i + 1) // bucket_size]
for i in range(bucket_size)
]
def __init__(self, a: Iterable[T] = []) -> None:
"Make a new SortedSet from iterable. / O(N) if sorted and unique / O(N log N)"
a = list(a)
if not all(a[i] < a[i + 1] for i in range(len(a) - 1)):
a = sorted(set(a))
self._build(a)
def __iter__(self) -> Iterator[T]:
for i in self.a:
for j in i:
yield j
def __reversed__(self) -> Iterator[T]:
for i in reversed(self.a):
for j in reversed(i):
yield j
def __len__(self) -> int:
return self.size
def __repr__(self) -> str:
return "SortedSet" + str(self.a)
def __str__(self) -> str:
s = str(list(self))
return "{" + s[1 : len(s) - 1] + "}"
def _find_bucket(self, x: T) -> List[T]:
"Find the bucket which should contain x. self must not be empty."
for a in self.a:
if x <= a[-1]:
return a
return a
def __contains__(self, x: T) -> bool:
if self.size == 0:
return False
a = self._find_bucket(x)
i = bisect_left(a, x)
return i != len(a) and a[i] == x
def add(self, x: T) -> bool:
"Add an element and return True if added. / O(√N)"
if self.size == 0:
self.a = [[x]]
self.size = 1
return True
a = self._find_bucket(x)
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return False
a.insert(i, x)
self.size += 1
if len(a) > len(self.a) * self.REBUILD_RATIO:
self._build()
return True
def discard(self, x: T) -> bool:
"Remove an element and return True if removed. / O(√N)"
if self.size == 0:
return False
a = self._find_bucket(x)
i = bisect_left(a, x)
if i == len(a) or a[i] != x:
return False
a.pop(i)
self.size -= 1
if len(a) == 0:
self._build()
return True
def lt(self, x: T) -> Union[T, None]:
"Find the largest element < x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] < x:
return a[bisect_left(a, x) - 1]
def le(self, x: T) -> Union[T, None]:
"Find the largest element <= x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] <= x:
return a[bisect_right(a, x) - 1]
def gt(self, x: T) -> Union[T, None]:
"Find the smallest element > x, or None if it doesn't exist."
for a in self.a:
if a[-1] > x:
return a[bisect_right(a, x)]
def ge(self, x: T) -> Union[T, None]:
"Find the smallest element >= x, or None if it doesn't exist."
for a in self.a:
if a[-1] >= x:
return a[bisect_left(a, x)]
def __getitem__(self, x: int) -> T:
"Return the x-th element, or IndexError if it doesn't exist."
if x < 0:
x += self.size
if x < 0:
raise IndexError
for a in self.a:
if x < len(a):
return a[x]
x -= len(a)
raise IndexError
def index(self, x: T) -> int:
"Count the number of elements < x."
ans = 0
for a in self.a:
if a[-1] >= x:
return ans + bisect_left(a, x)
ans += len(a)
return ans
def index_right(self, x: T) -> int:
"Count the number of elements <= x."
ans = 0
for a in self.a:
if a[-1] > x:
return ans + bisect_right(a, x)
ans += len(a)
return ans
# 宣言方法
# d = [SortedMultiset() for i in range(200001)]
# dv = [SortedSet() for i in range(200001)]
class UnionFind:
def __init__(self, n):
self.n = n
self.parents = [-1] * n
def find(self, x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def size(self, x):
return -self.parents[self.find(x)]
def same(self, x, y):
return self.find(x) == self.find(y)
def members(self, x): # 多用すると重い
root = self.find(x)
return [i for i in range(self.n) if self.find(i) == root]
def roots(self):
return [i for i, x in enumerate(self.parents) if x < 0]
def group_count(self):
return len(self.roots())
def all_group_members(self):
group_members = defaultdict(list)
for member in range(self.n):
group_members[self.find(member)].append(member)
return group_members
def __str__(self):
return "\n".join(f"{r}: {m}" for r, m in self.all_group_members().items())
# https://raw.githubusercontent.com/shakayami/ACL-for-python/master/segtree.py
class segtree:
n = 1
size = 1
log = 2
d = [0]
op = None
e = 10**15
def __init__(self, V, OP, E):
self.n = len(V)
self.op = OP
self.e = E
self.log = (self.n - 1).bit_length()
self.size = 1 << self.log
self.d = [E for i in range(2 * self.size)]
for i in range(self.n):
self.d[self.size + i] = V[i]
for i in range(self.size - 1, 0, -1):
self.update(i)
def set(self, p, x):
assert 0 <= p and p < self.n
p += self.size
self.d[p] = x
for i in range(1, self.log + 1):
self.update(p >> i)
def get(self, p):
assert 0 <= p and p < self.n
return self.d[p + self.size]
def prod(self, l, r):
assert 0 <= l and l <= r and r <= self.n
sml = self.e
smr = self.e
l += self.size
r += self.size
while l < r:
if l & 1:
sml = self.op(sml, self.d[l])
l += 1
if r & 1:
smr = self.op(self.d[r - 1], smr)
r -= 1
l >>= 1
r >>= 1
return self.op(sml, smr)
def all_prod(self):
return self.d[1]
def max_right(self, l, f):
assert 0 <= l and l <= self.n
assert f(self.e)
if l == self.n:
return self.n
l += self.size
sm = self.e
while 1:
while l % 2 == 0:
l >>= 1
if not (f(self.op(sm, self.d[l]))):
while l < self.size:
l = 2 * l
if f(self.op(sm, self.d[l])):
sm = self.op(sm, self.d[l])
l += 1
return l - self.size
sm = self.op(sm, self.d[l])
l += 1
if (l & -l) == l:
break
return self.n
def min_left(self, r, f):
assert 0 <= r and r <= self.n
assert f(self.e)
if r == 0:
return 0
r += self.size
sm = self.e
while 1:
r -= 1
while r > 1 and (r % 2):
r >>= 1
if not (f(self.op(self.d[r], sm))):
while r < self.size:
r = 2 * r + 1
if f(self.op(self.d[r], sm)):
sm = self.op(self.d[r], sm)
r -= 1
return r + 1 - self.size
sm = self.op(self.d[r], sm)
if (r & -r) == r:
break
return 0
def update(self, k):
self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
def __str__(self):
return str([self.get(i) for i in range(self.n)])
def get_list(self):
return [self.get(i) for i in range(self.n)] # オリジナルで追加
# RMQのとき
# def op(x, y):
# return x if x < y else y
# seg = segtree([10**9] * N, op, 10**9) # Vの要素とEの値は同じにする #10**9 -> INF
# seg.prod(l, r) # op(a[l],...a[r-1])を返す
# https://github.com/shakayami/ACL-for-python/blob/master/lazysegtree.py
class lazy_segtree:
def update(self, k):
self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
def all_apply(self, k, f):
self.d[k] = self.mapping(f, self.d[k])
if k < self.size:
self.lz[k] = self.composition(f, self.lz[k])
def push(self, k):
self.all_apply(2 * k, self.lz[k])
self.all_apply(2 * k + 1, self.lz[k])
self.lz[k] = self.identity
def __init__(self, V, OP, E, MAPPING, COMPOSITION, ID):
self.n = len(V)
self.log = (self.n - 1).bit_length()
self.size = 1 << self.log
self.d = [E for i in range(2 * self.size)]
self.lz = [ID for i in range(self.size)]
self.e = E
self.op = OP
self.mapping = MAPPING
self.composition = COMPOSITION
self.identity = ID
for i in range(self.n):
self.d[self.size + i] = V[i]
for i in range(self.size - 1, 0, -1):
self.update(i)
# Args:
# N (int): 配列の長さ
# op (Callable[[S, S], S]): 区間取得に用いる演算
# E: 全てのaに対して op(a, e) = a が成り立つ単位元
# MAPPING (Callable[[F, S], S]): dataに作用させる関数
# COMPOSITION (Callable[[F, F], F]): lazyに作用させる関数 f(g(x))
# ID: 全てのaに対して mapping(id, a) = a が成り立つ恒等写像
def set(self, p, x):
assert 0 <= p and p < self.n
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
self.d[p] = x
for i in range(1, self.log + 1):
self.update(p >> i)
def get(self, p):
assert 0 <= p and p < self.n
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
return self.d[p]
def prod(self, l, r):
assert 0 <= l and l <= r and r <= self.n
if l == r:
return self.e
l += self.size
r += self.size
for i in range(self.log, 0, -1):
if ((l >> i) << i) != l:
self.push(l >> i)
if ((r >> i) << i) != r:
self.push(r >> i)
sml, smr = self.e, self.e
while l < r:
if l & 1:
sml = self.op(sml, self.d[l])
l += 1
if r & 1:
r -= 1
smr = self.op(self.d[r], smr)
l >>= 1
r >>= 1
return self.op(sml, smr)
def all_prod(self):
return self.d[1]
def apply_point(self, p, f):
assert 0 <= p and p < self.n
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
self.d[p] = self.mapping(f, self.d[p])
for i in range(1, self.log + 1):
self.update(p >> i)
def apply(self, l, r, f):
assert 0 <= l and l <= r and r <= self.n
if l == r:
return
l += self.size
r += self.size
for i in range(self.log, 0, -1):
if ((l >> i) << i) != l:
self.push(l >> i)
if ((r >> i) << i) != r:
self.push((r - 1) >> i)
l2, r2 = l, r
while l < r:
if l & 1:
self.all_apply(l, f)
l += 1
if r & 1:
r -= 1
self.all_apply(r, f)
l >>= 1
r >>= 1
l, r = l2, r2
for i in range(1, self.log + 1):
if ((l >> i) << i) != l:
self.update(l >> i)
if ((r >> i) << i) != r:
self.update((r - 1) >> i)
def max_right(self, l, g):
assert 0 <= l and l <= self.n
assert g(self.e)
if l == self.n:
return self.n
l += self.size
for i in range(self.log, 0, -1):
self.push(l >> i)
sm = self.e
while 1:
while l % 2 == 0:
l >>= 1
if not (g(self.op(sm, self.d[l]))):
while l < self.size:
self.push(l)
l = 2 * l
if g(self.op(sm, self.d[l])):
sm = self.op(sm, self.d[l])
l += 1
return l - self.size
sm = self.op(sm, self.d[l])
l += 1
if (l & -l) == l:
break
return self.n
def min_left(self, r, g):
assert 0 <= r and r <= self.n
assert g(self.e)
if r == 0:
return 0
r += self.size
for i in range(self.log, 0, -1):
self.push((r - 1) >> i)
sm = self.e
while 1:
r -= 1
while r > 1 and (r % 2):
r >>= 1
if not (g(self.op(self.d[r], sm))):
while r < self.size:
self.push(r)
r = 2 * r + 1
if g(self.op(self.d[r], sm)):
sm = self.op(self.d[r], sm)
r -= 1
return r + 1 - self.size
sm = self.op(self.d[r], sm)
if (r & -r) == r:
break
return 0
# ACLのではない。機能は減るが、こっちのほうが早い
class LazySegTree:
def __init__(self, v, op, e, mapping, composition, id_):
n = len(v)
self._op = op
self._e = e
self._mapping = mapping
self._composition = composition
self._id = id_
self._size = 1 << (n - 1).bit_length()
self._d = [e] * (2 * self._size)
self._lz = [id_] * 2 * self._size
for i in range(n):
self._d[self._size + i] = v[i]
for i in range(self._size - 1, 0, -1):
self._d[i] = self._op(self._d[2 * i], self._d[2 * i + 1])
def _gindex(self, l, r):
l += self._size
r += self._size
lm = l >> (l & -l).bit_length()
rm = r >> (r & -r).bit_length()
while r > l:
if l <= lm:
yield l
if r <= rm:
yield r
l >>= 1
r >>= 1
while l:
yield l
l >>= 1
def _propagates(self, *ids):
for i in reversed(ids):
f = self._lz[i]
self._lz[i] = self._id
self._lz[2 * i] = self._composition(f, self._lz[2 * i])
self._lz[2 * i + 1] = self._composition(f, self._lz[2 * i + 1])
self._d[2 * i] = self._mapping(f, self._d[2 * i])
self._d[2 * i + 1] = self._mapping(f, self._d[2 * i + 1])
def apply(self, l, r, f):
(*ids,) = self._gindex(l, r)
self._propagates(*ids)
l += self._size
r += self._size
while l < r:
if l & 1:
self._lz[l] = self._composition(f, self._lz[l])
self._d[l] = self._mapping(f, self._d[l])
l += 1
if r & 1:
self._lz[r - 1] = self._composition(f, self._lz[r - 1])
self._d[r - 1] = self._mapping(f, self._d[r - 1])
l >>= 1
r >>= 1
for i in ids:
self._d[i] = self._op(self._d[2 * i], self._d[2 * i + 1])
def prod(self, l, r):
self._propagates(*self._gindex(l, r))
resl = self._e
resr = self._e
l += self._size
r += self._size
while l < r:
if l & 1:
resl = self._op(resl, self._d[l])
l += 1
if r & 1:
resr = self._op(self._d[r - 1], resr)
l >>= 1
r >>= 1
return self._op(resl, resr)
# RMQのとき
# def op(a, b):
# if a > b:
# return b
# return a
# def mapping(f, x): # 更新(dataに作用, fは上書きフラグ(f==ID: False))
# if f == ID:
# return x
# return f
# def composition(f, g): # 更新(lazyに作用, fは上書きフラグ(f==ID: False), 作用順はg→f)
# if f == ID:
# return g
# return f
# ini = INF
# ID = ini
# lst = lazy_segtree([ini] * len(d), op, ini, mapping, composition, ID)
# lst.apply(l, r, x)
# lst.prod(l, r)
# RAQのとき
# def mapping(f, x):
# return f + x
# def composition(f, g):
# return f + g
# https://github.com/shakayami/ACL-for-python/blob/master/string.py
class string:
def sa_is(s, upper):
n = len(s)
if n == 0:
return []
if n == 1:
return [0]
if n == 2:
if s[0] < s[1]:
return [0, 1]
else:
return [1, 0]
sa = [0] * n
ls = [0] * n
for i in range(n - 2, -1, -1):
ls[i] = ls[i + 1] if (s[i] == s[i + 1]) else (s[i] < s[i + 1])
sum_l = [0] * (upper + 1)
sum_s = [0] * (upper + 1)
for i in range(n):
if not (ls[i]):
sum_s[s[i]] += 1
else:
sum_l[s[i] + 1] += 1
for i in range(upper + 1):
sum_s[i] += sum_l[i]
if i < upper:
sum_l[i + 1] += sum_s[i]
def induce(lms):
for i in range(n):
sa[i] = -1
buf = sum_s[:]
for d in lms:
if d == n:
continue
sa[buf[s[d]]] = d
buf[s[d]] += 1
buf = sum_l[:]
sa[buf[s[n - 1]]] = n - 1
buf[s[n - 1]] += 1
for i in range(n):
v = sa[i]
if v >= 1 and not (ls[v - 1]):
sa[buf[s[v - 1]]] = v - 1
buf[s[v - 1]] += 1
buf = sum_l[:]
for i in range(n - 1, -1, -1):
v = sa[i]
if v >= 1 and ls[v - 1]:
buf[s[v - 1] + 1] -= 1
sa[buf[s[v - 1] + 1]] = v - 1
lms_map = [-1] * (n + 1)
m = 0
for i in range(1, n):
if not (ls[i - 1]) and ls[i]:
lms_map[i] = m
m += 1
lms = []
for i in range(1, n):
if not (ls[i - 1]) and ls[i]:
lms.append(i)
induce(lms)
if m:
sorted_lms = []
for v in sa:
if lms_map[v] != -1:
sorted_lms.append(v)
rec_s = [0] * m
rec_upper = 0
rec_s[lms_map[sorted_lms[0]]] = 0
for i in range(1, m):
l = sorted_lms[i - 1]
r = sorted_lms[i]
end_l = lms[lms_map[l] + 1] if (lms_map[l] + 1 < m) else n
end_r = lms[lms_map[r] + 1] if (lms_map[r] + 1 < m) else n
same = True
if end_l - l != end_r - r:
same = False
else:
while l < end_l:
if s[l] != s[r]:
break
l += 1
r += 1
if (l == n) or (s[l] != s[r]):
same = False
if not (same):
rec_upper += 1
rec_s[lms_map[sorted_lms[i]]] = rec_upper
rec_sa = string.sa_is(rec_s, rec_upper)
for i in range(m):
sorted_lms[i] = lms[rec_sa[i]]
induce(sorted_lms)
return sa
def suffix_array_upper(s, upper):
assert 0 <= upper
for d in s:
assert 0 <= d and d <= upper
return string.sa_is(s, upper)
def suffix_array(s):
n = len(s)
if type(s) == str:
s2 = [ord(i) for i in s]
return string.sa_is(s2, 255)
else:
idx = list(range(n))
idx.sort(key=lambda x: s[x])
s2 = [0] * n
now = 0
for i in range(n):
if i & s[idx[i - 1]] != s[idx[i]]:
now += 1
s2[idx[i]] = now
return string.sa_is(s2, now)
def lcp_array(s, sa):
n = len(s)
assert n >= 1
rnk = [0] * n
for i in range(n):
rnk[sa[i]] = i
lcp = [0] * (n - 1)
h = 0
for i in range(n):
if h > 0:
h -= 1
if rnk[i] == 0:
continue
j = sa[rnk[i] - 1]
while j + h < n and i + h < n:
if s[j + h] != s[i + h]:
break
h += 1
lcp[rnk[i] - 1] = h
return lcp
def z_algorithm(s):
n = len(s)
if n == 0:
return []
z = [0] * n
i = 1
j = 0
while i < n:
z[i] = 0 if (j + z[j] <= i) else min(j + z[j] - i, z[i - j])
while (i + z[i] < n) and (s[z[i]] == s[i + z[i]]):
z[i] += 1
if j + z[j] < i + z[i]:
j = i
i += 1
z[0] = n
return z
# suffix_arrayの作り方
# S = "abcababaabc"
# sa = string.suffix_array(S)
# lcp = string.lcp_array(S, sa)
class BIT:
def __init__(self, n):
self.n = len(n) if isinstance(n, list) else n
self.size = 1 << (self.n - 1).bit_length()
if isinstance(n, list): # nは1-indexedなリスト
a = [0]
for p in n:
a.append(p + a[-1])
a += [a[-1]] * (self.size - self.n)
self.d = [a[p] - a[p - (p & -p)] for p in range(self.size + 1)]
else: # nは大きさ
self.d = [0] * (self.size + 1)
def __repr__(self):
p = self.size
res = []
while p > 0:
res2 = []
for r in range(p, self.size + 1, p * 2):
l = r - (r & -r) + 1
res2.append(f"[{l}, {r}]:{self.d[r]}")
res.append(" ".join(res2))
p >>= 1
res.append(f"{[self.sum(p + 1) - self.sum(p) for p in range(self.size)]}")
return "\n".join(res)
def add(self, p, x): # O(log(n)), 点pにxを加算
assert p > 0
while p <= self.size:
self.d[p] += x
p += p & -p
def get(self, p, default=None): # O(log(n))
assert p > 0
return (
self.sum(p) - self.sum(p - 1)
if 1 <= p <= self.n or default is None
else default
)
def sum(self, p): # O(log(n)), 閉区間[1, p]の累積和
assert p >= 0
res = 0
while p > 0:
res += self.d[p]
p -= p & -p
return res
def lower_bound(self, x): # O(log(n)), x <= 閉区間[1, p]の累積和 となる最小のp
if x <= 0:
return 0
p, r = 0, self.size
while r > 0:
if p + r <= self.n and self.d[p + r] < x:
x -= self.d[p + r]
p += r
r >>= 1
return p + 1
class MultiSet:
# n: サイズ、compress: 座圧対象list-likeを指定(nは無効)
# multi: マルチセットか通常のOrderedSetか
def __init__(self, n=0, *, compress=[], multi=True):
self.multi = multi
self.inv_compress = (
sorted(set(compress)) if len(compress) > 0 else [i for i in range(n)]
)
self.compress = {k: v for v, k in enumerate(self.inv_compress)}
self.counter_all = 0
self.counter = [0] * len(self.inv_compress)
self.bit = BIT(len(self.inv_compress))
def add(self, x, n=1): # O(log n)
if not self.multi and n != 1:
raise KeyError(n)
x = self.compress[x]
count = self.counter[x]
if count == 0 or self.multi: # multiなら複数カウントできる
self.bit.add(x + 1, n)
self.counter_all += n
self.counter[x] += n
def remove(self, x, n=1): # O(log n)
if not self.multi and n != 1:
raise KeyError(n)
x = self.compress[x]
count = self.bit.get(x + 1)
if count < n:
raise KeyError(x)
self.bit.add(x + 1, -n)
self.counter_all -= n
self.counter[x] -= n
def __repr__(self):
return f'MultiSet {{{(", ".join(map(str, list(self))))}}}'
def __len__(self): # oprator len: O(1)
return self.counter_all
def count(self, x): # O(1)
return self.counter[self.compress[x]] if x in self.compress else 0
def __getitem__(self, i): # operator []: O(log n)
if i < 0:
i += len(self)
x = self.bit.lower_bound(i + 1)
if x > self.bit.n:
raise IndexError("list index out of range")
return self.inv_compress[x - 1]
def __contains__(self, x): # operator in: O(1)
return self.count(x) > 0
def bisect_left(self, x): # O(log n)
return self.bit.sum(bisect.bisect_left(self.inv_compress, x))
def bisect_right(self, x): # O(log n)
return self.bit.sum(bisect.bisect_right(self.inv_compress, x))
# 宣言方法
# MultiSet(compress=X,multi=False)
# MultiSet(N+1,multi=True)
# リストを渡すと座標圧縮して返してくれる
def compress(arr):
(*XS,) = set(arr)
XS.sort()
return {cmp_e: cmp_i for cmp_i, cmp_e in enumerate(XS)}
def ctov(c):
return ord(c) - ord("a")
def CTOV(c):
return ord(c) - ord("A")
# 約数列挙
def make_divisors(n):
lower_divisors, upper_divisors = [], []
i = 1
while i * i <= n:
if n % i == 0:
lower_divisors.append(i)
if i != n // i:
upper_divisors.append(n // i)
i += 1
return lower_divisors + upper_divisors[::-1]
# 素因数分解(辞書)
def prime_factorize(n):
V = defaultdict(int)
i = 2
while i**2 <= n:
while n % i == 0:
V[i] += 1
n //= i
i += 1
if n != 1:
V[n] += 1
return V
def convert_90(matrix):
# 入力行列の行数と列数を取得
rows = len(matrix)
cols = len(matrix[0])
# 90度回転後の行列を初期化
rotated_matrix = [[0] * rows for _ in range(cols)]
# 元の行列を90度回転させて新しい行列に格納
for i in range(rows):
for j in range(cols):
rotated_matrix[j][rows - 1 - i] = matrix[i][j]
return rotated_matrix
def cropping(MAP, mark):
M_y, M_x = 0, 0
m_y, m_x = INF, INF
H, W = len(MAP), len(MAP[0])
for i in range(H):
for j in range(W):
if MAP[i][j] == mark:
M_y = max(i, M_y)
M_x = max(M_x, j)
m_y = min(i, m_y)
m_x = min(m_x, j)
new = [[0] * (M_x - m_x + 1) for _ in range(M_y - m_y + 1)]
for i in range(m_y, M_y + 1):
for j in range(m_x, M_x + 1):
new[i - m_y][j - m_x] = MAP[i][j]
return new
def cos(theta):
theta_rad = math.radians(theta)
cos_value = math.cos(theta_rad)
return cos_value
return math.acos(val)
def sin(theta):
theta_rad = math.radians(theta)
sin_value = math.sin(theta_rad)
return sin_value
def acos(value):
radians = math.acos(value)
degrees = math.degrees(radians)
return degrees
# ダブリング dp[i][j]:=jから2**i回遷移したときの到達点
# https://atcoder.jp/contests/abc167/submissions/40815296
# N,K=map(int,input().split())
# A=list(map(int,input().split()))
# dp=[[-1]*N for _ in range(60)]
# for j in range(N):
# dp[0][j]=A[j]-1
# for i in range(1,60):
# for j in range(N):
# dp[i][j]=dp[i-1][dp[i-1][j]]
# i=0
# now=0
# while(K>0):
# if (K&1)==1:
# now=dp[i][now]
# i+=1
# K>>=1
# print(now+1)
# 牛ゲー
# xj-xi<=bkの条件の下で、xt-xsを最大化する問題
# i→jへ、重みbkの有効辺をはったとき、sからtまでの最短距離がxt-xsの最大値と一致する。
# 到達できない場合は、xt-xsは無限大
dxdy1 = ((0, 1), (0, -1), (1, 0), (-1, 0))
dxdy2 = ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1))
dxdy3 = ((0, 1), (1, 0))
dxdy4 = ((1, 1), (1, -1), (-1, 1), (-1, -1))
INF = float("inf")
MOD = 998244353
mod = 998244353
MOD2 = 10**9 + 7
mod2 = 10**9 + 7
# memo : len([a,b,...,z])==26
T = int(input())
for _ in range(T):
a, b, k = map(int, input().split())
lcm = a*b//math.gcd(a, b)
ok = 10**20
ng = 0
while ok - ng > 1:
mid = (ok + ng) // 2
t1 = mid // a
t2 = mid // b
t3 = mid // lcm
tmp = mid - t1 - t2 + t3
if tmp >= k:
ok = mid
else:
ng = mid
print(ok)