結果
問題 |
No.1022 Power Equation
|
ユーザー |
![]() |
提出日時 | 2025-04-09 21:05:13 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,270 bytes |
コンパイル時間 | 305 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 366,780 KB |
最終ジャッジ日時 | 2025-04-09 21:06:50 |
合計ジャッジ時間 | 4,252 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 TLE * 1 -- * 6 |
ソースコード
import sys import math def is_perfect_power(x): if x == 1: return False max_e = int(math.log2(x)) + 1 for e in range(2, max_e + 1): a = round(x ** (1.0 / e)) if a ** e == x or (a + 1) ** e == x: return True return False def solve(): input = sys.stdin.read().split() T = int(input[0]) cases = list(map(int, input[1:T+1])) for N in cases: if N == 0: print(0) continue # Calculate perfect powers perfect_powers = set() max_e = int(math.log2(N)) + 1 if N > 1 else 0 for e in range(2, max_e + 1): a = 2 while True: val = a ** e if val > N: break if val <= N: perfect_powers.add(val) a += 1 # Primitives are numbers from 1 to N that are not in perfect_powers primitives = [] for x in range(1, N + 1): if x == 1: primitives.append(1) else: if not is_perfect_power(x): primitives.append(x) count = {} # Handle x = 1 # x=1, a=1^1, m=1*b for b=1..N → V=1^b =1 for all b count[1] = count.get(1, 0) + N # Process other primitives for x in primitives: if x == 1: continue max_k = 1 while True: xk = x ** max_k if xk > N: max_k -= 1 break max_k += 1 if max_k == 0: continue for k in range(1, max_k + 1): # x^k is the a here a = x ** k if a > N: continue # For each b in 1..N, V=x^(k*b) # Compute min and max possible k*b max_m = k * N current_m_base = k for b in range(1, N + 1): m = k * b v = x ** m count[v] = count.get(v, 0) + 1 total = sum(c * c for c in count.values()) print(total) if __name__ == "__main__": solve()