結果
問題 | No.1666 累乗数 |
ユーザー | Kiri8128 |
提出日時 | 2021-09-03 23:01:23 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 864 bytes |
コンパイル時間 | 291 ms |
コンパイル使用メモリ | 86,932 KB |
実行使用メモリ | 79,344 KB |
最終ジャッジ日時 | 2023-08-22 00:26:59 |
合計ジャッジ時間 | 30,832 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 116 ms
77,120 KB |
testcase_01 | AC | 702 ms
78,184 KB |
testcase_02 | AC | 712 ms
78,452 KB |
testcase_03 | AC | 717 ms
78,156 KB |
testcase_04 | AC | 720 ms
78,152 KB |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
testcase_09 | AC | 989 ms
78,248 KB |
testcase_10 | AC | 1,033 ms
78,832 KB |
testcase_11 | AC | 1,047 ms
78,276 KB |
testcase_12 | AC | 1,032 ms
78,976 KB |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | AC | 1,361 ms
78,636 KB |
testcase_18 | AC | 1,589 ms
78,628 KB |
testcase_19 | AC | 1,329 ms
78,372 KB |
ソースコード
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)