結果
問題 | No.1666 累乗数 |
ユーザー | Kiri8128 |
提出日時 | 2021-09-03 23:07:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,715 ms / 2,000 ms |
コード長 | 1,279 bytes |
コンパイル時間 | 321 ms |
コンパイル使用メモリ | 87,112 KB |
実行使用メモリ | 78,824 KB |
最終ジャッジ日時 | 2023-08-22 00:42:03 |
合計ジャッジ時間 | 23,198 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 112 ms
77,164 KB |
testcase_01 | AC | 547 ms
78,320 KB |
testcase_02 | AC | 540 ms
78,276 KB |
testcase_03 | AC | 542 ms
78,076 KB |
testcase_04 | AC | 541 ms
78,012 KB |
testcase_05 | AC | 1,689 ms
78,592 KB |
testcase_06 | AC | 1,715 ms
78,452 KB |
testcase_07 | AC | 1,703 ms
78,184 KB |
testcase_08 | AC | 1,708 ms
78,392 KB |
testcase_09 | AC | 760 ms
78,372 KB |
testcase_10 | AC | 803 ms
78,396 KB |
testcase_11 | AC | 812 ms
77,944 KB |
testcase_12 | AC | 796 ms
78,156 KB |
testcase_13 | AC | 1,571 ms
78,364 KB |
testcase_14 | AC | 1,568 ms
78,196 KB |
testcase_15 | AC | 1,561 ms
78,824 KB |
testcase_16 | AC | 1,570 ms
78,428 KB |
testcase_17 | AC | 1,008 ms
78,132 KB |
testcase_18 | AC | 1,187 ms
78,648 KB |
testcase_19 | AC | 966 ms
78,192 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 WW1: s += w * (sqrt(n, b) - 1) for b, w in WW2: if n >= 2 ** b: s += w 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)] WW1 = [(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)] WW2 = [(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)