結果
問題 | No.2526 Kth Not-divisible Number |
ユーザー |
|
提出日時 | 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 |
ソースコード
import sys#sys.setrecursionlimit(10 ** 6)#sys.set_int_max_str_digits(0)INF = float('inf')MOD = 10**9 + 7MOD2 = 998244353from collections import defaultdictdef ceil(A,B):return -(-A//B)import mathdef 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条件の付け方は、ngとokの広げ方をどのようにするかで決まってくる。負の無限~(目的値)が条件を満たす場合ng…条件を満たさない値の範囲での最小値ok…条件を満たす値の範囲での最大値ok < ngis_ok == Trueの場合、探索範囲が右半分へis_ok == Falseの場合、探索範囲が左半分へ(目的値)~正の無限 が条件を満たす場合ng…条件を満たさない値の範囲での最大値ok…条件を満たす値の範囲での最小値ng < okis_ok == Trueの場合、探索範囲が左半分へis_ok == Falseの場合、探索範囲が右半分へ"""while (abs(ok - ng) > 1):mid = (ok + ng) // 2if is_ok(mid):ok = midelse:ng = midreturn okfor test in range(T):A,B,K = MI()LCM = my_lcm(A,B)a_num = (LCM-1)//Ab_num = (LCM-1)//Bk_num = LCM-(a_num+b_num)-1#print(k_num,K)P = K//k_numif(K%k_num==0):P-=1Ans = P*LCMK-= k_num*P#print(k_num,P,K)add = 0if(1<=K):def is_ok(n):A_n = n//AB_n = n//Breturn K<= n-(A_n+B_n)add = meguru_bisect(0,LCM)print(Ans+add)returnsolve()