結果
問題 | No.1666 累乗数 |
ユーザー |
![]() |
提出日時 | 2021-09-03 23:01:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,773 ms / 2,000 ms |
コード長 | 864 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 82,724 KB |
実行使用メモリ | 77,804 KB |
最終ジャッジ日時 | 2024-12-15 16:55:34 |
合計ジャッジ時間 | 23,067 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 19 |
ソースコード
def sqrt(n, k = 2): if n == 0: return 0 l = k - 1 if not n: return 0 y = 1 << (n.bit_length() + l) // k x = y + 1 while y < x: x = y y = (l * x + n // (x ** l)) // k return x def cnt(n): s = 1 for b, w in WW: s += w * (sqrt(n, b) - 1) return s WW = [(2, 1), (3, 1), (5, 1), (6, -1), (7, 1), (10, -1), (11, 1), (13, 1), (14, -1), (15, -1), (17, 1), (19, 1), (21, -1), (22, -1), (23, 1), (26, -1), (29, 1), (30, 1), (31, 1), (33, -1), (34, -1), (35, -1), (37, 1), (38, -1), (39, -1), (41, 1), (42, 1), (43, 1), (46, -1), (47, 1), (51, -1), (53, 1), (55, -1), (57, -1), (58, -1), (59, 1)] T = int(input()) for _ in range(T): K = int(input()) l, r = 0, 10 ** 18 while r - l > 1: m = l + r >> 1 if cnt(m) < K: l = m else: r = m print(r)