結果
問題 |
No.2526 Kth Not-divisible Number
|
ユーザー |
|
提出日時 | 2023-11-03 22:03:24 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,079 bytes |
コンパイル時間 | 138 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 17,828 KB |
最終ジャッジ日時 | 2024-09-25 20:23:05 |
合計ジャッジ時間 | 4,132 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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): kk = m - ((m//a + m//b) - m//lcm(a,b)) if kk <= k: return 1 else: return 0 def sol(): a,b,k = map(int,input().split()) ok=0 ng=3*10**18 while ng-ok>1: mid=(ng+ok)//2 if judge(a,b,k,mid): 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