結果
問題 |
No.2526 Kth Not-divisible Number
|
ユーザー |
|
提出日時 | 2023-11-03 22:26:54 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,095 bytes |
コンパイル時間 | 471 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 16,384 KB |
最終ジャッジ日時 | 2024-09-25 20:50:40 |
合計ジャッジ時間 | 4,413 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 WA * 1 TLE * 1 -- * 8 |
ソースコード
import sys sys.setrecursionlimit(5*10**5) input = sys.stdin.readline sys.set_int_max_str_digits(0) from collections import defaultdict, deque, Counter from heapq import heappop, heappush from bisect import bisect_left, bisect_right from math import gcd, lcm, factorial, perm, comb from itertools import product, permutations #重複あり:list(product(list('123'),repeat = 2)),重複なし:list(permutations(list('123'))) MOD = 998244353 def judge(a,b,k,m,lc): kk = m - ((m//a + m//b) - m//lc) if kk <= k: return 1 else: return 0 def sol(): a,b,k = map(int,input().split()) ok=0 ng=3*10**18 lc=lcm(a,b) while ng-ok>1: mid=(ng+ok)//2 if judge(a,b,k,mid,lc): ok=mid else: ng=mid print(ok) T = int(input()) for i in range(T): sol() #100のうち5の倍数は20個、100のうち3の倍数は33個 #53個から15の倍数は除く6個、47個が3と5の倍数 #2分探索で行けるのでは #正整数nがK番目のより大きいか小さいか。 #(n - (n//a + n//b - n//(a*b)))->K