結果

問題 No.3236 累乗数大好きbot
ユーザー 回転
提出日時 2025-08-15 22:11:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,311 bytes
コンパイル時間 1,951 ms
コンパイル使用メモリ 210,720 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-15 22:12:30
合計ジャッジ時間 13,678 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 2 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
from collections import defaultdict
def prime_factorize(n):
    # https://note.nkmk.me/python-prime-factorization/
    a = defaultdict(int)
    while n % 2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] += 1
    return a

def sieve_of_eratosthenes(n):
    # https://af-e.net/python-sieve-of-eratosthenes/
    primes = [True] * (n + 1)
    p = 2
    while (p * p <= n):
        if primes[p]:
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1
    return [p for p in range(2, n + 1) if primes[p]]
p = sieve_of_eratosthenes(10**6)

ans = []
Q = int(input())
for _ in range(Q):
    N = int(input())
    a = set(prime_factorize(N).values())
    
    for i in range(60,0,-1):
        if(all([x%i == 0 for x in a])):
            ans.append(str(i))
            break

print("\n".join(ans))
*/

#include <bits/stdc++.h>
using namespace std;

unordered_map<long long,int> prime_factorize(long long n){
    unordered_map<long long,int> a;
    while (n % 2 == 0){
        a[2]++;
        n /= 2;
    }
    long long f = 3;
    while (f * f <= n){
        if (n % f == 0){
            a[f]++;
            n /= f;
        } else {
            f += 2;
        }
    }
    if (n != 1) a[n]++;
    return a;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int Q;
    if (!(cin >> Q)) return 0;
    vector<string> ans;
    for (int qi = 0; qi < Q; ++qi){
        long long N;
        cin >> N;
        auto fac = prime_factorize(N);
        unordered_set<int> exps;
        for (auto &kv : fac) exps.insert(kv.second);
        // replicate Python's behavior: if exps is empty, all([]) is True, so first i (60) is chosen.
        for (int i = 60; i >= 1; --i){
            bool ok = true;
            for (int x : exps){
                if (x % i != 0){
                    ok = false;
                    break;
                }
            }
            if (ok){
                ans.push_back(to_string(i));
                break;
            }
        }
    }
    for (size_t i = 0; i < ans.size(); ++i){
        if (i) cout << '\n';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}
0