結果
問題 |
No.1022 Power Equation
|
ユーザー |
![]() |
提出日時 | 2025-03-26 15:56:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 324 ms / 2,000 ms |
コード長 | 2,047 bytes |
コンパイル時間 | 230 ms |
コンパイル使用メモリ | 82,660 KB |
実行使用メモリ | 95,756 KB |
最終ジャッジ日時 | 2025-03-26 15:57:04 |
合計ジャッジ時間 | 2,575 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 8 |
ソースコード
import math import sys def compute_T(k, N): if k == 0: return 0 if k == 1: return N low = 1 high = N best = 0 while low <= high: mid = (low + high) // 2 product = 1 overflow = False for _ in range(k): product *= mid if product > N: overflow = True break if overflow: high = mid - 1 else: best = mid low = mid + 1 return best def count_perfect_powers(T): if T < 2: return 0 perfect = set() max_e = 1 while (2 ** (max_e + 1)) <= T: max_e += 1 for e in range(2, max_e + 1): x_max = compute_T(e, T) if x_max < 2: continue for x in range(2, x_max + 1): pe = x ** e if pe > T: continue perfect.add(pe) return len(perfect) def solve(): input = sys.stdin.read().split() T_cases = int(input[0]) cases = list(map(int, input[1:T_cases+1])) for N in cases: ans = N * N # Contribution from t=1 if N == 0: print(0) continue max_k = 1 while (2 ** max_k) <= N: max_k += 1 max_k -= 1 if max_k < 1: print(ans) continue for k1 in range(1, max_k + 1): T1 = compute_T(k1, N) for k2 in range(1, max_k + 1): T2 = compute_T(k2, N) T = min(T1, T2) if T < 2: continue perfect = count_perfect_powers(T) non_perfect = T - 1 - perfect if non_perfect <= 0: continue g = math.gcd(k1, k2) s1 = (N * g) // k2 s2 = (N * g) // k1 s_max = min(s1, s2) if s_max < 1: continue ans += non_perfect * s_max print(ans) if __name__ == "__main__": solve()