結果

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

ソースコード

diff # 

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