結果

問題 No.1022 Power Equation
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0