結果

問題 No.2526 Kth Not-divisible Number
ユーザー moharan627
提出日時 2023-11-03 21:53:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 447 ms / 2,000 ms
コード長 2,206 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 81,888 KB
実行使用メモリ 78,072 KB
最終ジャッジ日時 2024-09-25 20:05:39
合計ジャッジ時間 4,895 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
#sys.setrecursionlimit(10 ** 6)
#sys.set_int_max_str_digits(0)
INF = float('inf')
MOD = 10**9 + 7
MOD2 = 998244353
from collections import defaultdict
def ceil(A,B):
return -(-A//B)
import math
def my_lcm(x, y):
return (x * y) // math.gcd(x, y)
def solve():
def II(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LC(): return list(sys.stdin.readline().rstrip())
def IC(): return [int(c) for c in sys.stdin.readline().rstrip()]
def MI(): return map(int, sys.stdin.readline().split())
T = II()
def meguru_bisect(ng, ok):
"""
OK
ngok
(
ng…
ok…
ok < ng
is_ok == True
is_ok == False
ng…
ok…
ng < ok
is_ok == True
is_ok == False
"""
while (abs(ok - ng) > 1):
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
return ok
for test in range(T):
A,B,K = MI()
LCM = my_lcm(A,B)
a_num = (LCM-1)//A
b_num = (LCM-1)//B
k_num = LCM-(a_num+b_num)-1
#print(k_num,K)
P = K//k_num
if(K%k_num==0):
P-=1
Ans = P*LCM
K-= k_num*P
#print(k_num,P,K)
add = 0
if(1<=K):
def is_ok(n):
A_n = n//A
B_n = n//B
return K<= n-(A_n+B_n)
add = meguru_bisect(0,LCM)
print(Ans+add)
return
solve()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0