#1112875 (C++17) No.3236 累乗数大好きbot

• 問題: No.3236 累乗数大好きbot
• ユーザー: 回転
• 提出日時: 2025-08-15 22:17:02
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 3,696 ms / 4,000 ms
• コード長: 6,736 bytes
• コンパイル時間: 2,118 ms
• コンパイル使用メモリ: 211,772 KB
• 実行使用メモリ: 9,068 KB
• 最終ジャッジ日時: 2025-08-15 22:18:30
• 合計ジャッジ時間: 55,608 ms
• ジャッジサーバーID （参考情報）: judge1 / judge6

ファイルパターン	結果
sample	AC * 1
other	AC * 31

ソースコード

/* Original Python code (kept at the beginning as required)
from collections import defaultdict
def gcd(a, b):
    while a:
        a, b = b%a, a
    return b


def is_prime(n):
    if n == 2:
        return 1
    if n == 1 or n%2 == 0:
        return 0

    m = n - 1
    lsb = m & -m
    s = lsb.bit_length()-1
    d = m // lsb

    test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

    for a in test_numbers:
        if a == n:
            continue
        x = pow(a,d,n)
        r = 0
        if x == 1:
            continue
        while x != m:
            x = pow(x,2,n)
            r += 1
            if x == 1 or r == s:
                return 0
    return 1


def find_prime_factor(n):
    if n%2 == 0:
        return 2

    m = int(n**0.125)+1

    for c in range(1,n):
        f = lambda a: (pow(a,2,n)+c)%n
        y = 0
        g = q = r = 1
        k = 0
        while g == 1:
            x = y
            while k < 3*r//4:
                y = f(y)
                k += 1
            while k < r and g == 1:
                ys = y
                for _ in range(min(m, r-k)):
                    y = f(y)
                    q = q*abs(x-y)%n
                g = gcd(q,n)
                k += m
            k = r
            r *= 2
        if g == n:
            g = 1
            y = ys
            while g == 1:
                y = f(y)
                g = gcd(abs(x-y),n)
        if g == n:
            continue
        if is_prime(g):
            return g
        elif is_prime(n//g):
            return n//g
        else:
            return find_prime_factor(g)


def factorize(n):
    res = {}
    while not is_prime(n) and n > 1:  # nが合成数である間nの素因数の探索を繰り返す
        p = find_prime_factor(n)
        s = 0
        while n%p == 0:  # nが素因数pで割れる間割り続け、出力に追加
            n //= p
            s += 1
        res[p] = s
    if n > 1:  # n>1であればnは素数なので出力に追加
        res[n] = 1
    return res


ans = []
Q = int(input())
for _ in range(Q):
    N = int(input())
    a = set(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;

using u64 = unsigned long long;
using u128 = __uint128_t;
using i128 = __int128_t;

u64 gcd_u64(u64 a, u64 b){
    while(a){
        u64 t = b % a;
        b = a;
        a = t;
    }
    return b;
}

u64 mul_mod(u64 a, u64 b, u64 mod){
    return (u128)a * b % mod;
}

u64 pow_mod(u64 a, u64 e, u64 mod){
    u128 res = 1;
    u128 base = a % mod;
    while(e){
        if(e & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        e >>= 1;
    }
    return (u64)res;
}

// Miller-Rabin primality test (keeps same small-base list as Python version)
bool is_prime(u64 n){
    if(n == 2) return true;
    if(n < 2 || (n % 2 == 0)) return false;

    u64 m = n - 1;
    u64 lsb = m & (~m + 1); // m & -m
    int s = 0;
    u64 tmp = lsb;
    while(tmp > 1){ tmp >>= 1; ++s; } // s = lsb.bit_length() - 1 in python
    if(lsb == 1) s = 0;
    // compute d = m // lsb
    u64 d = m / lsb;

    const u64 test_numbers_arr[] = {2ULL,3ULL,5ULL,7ULL,11ULL,13ULL,17ULL,19ULL,23ULL,29ULL,31ULL,37ULL};
    for(u64 a : test_numbers_arr){
        if(a == n) continue;
        u64 x = pow_mod(a, d, n);
        int r = 0;
        if(x == 1) continue;
        while(x != m){
            x = mul_mod(x, x, n);
            r += 1;
            if(x == 1 || r == s) return false;
        }
    }
    return true;
}

// Pollard-Brent style factor finder translated from the Python code
u64 find_prime_factor(u64 n){
    if(n % 2 == 0) return 2;
    // m = int(n**0.125) + 1
    // compute integer floor of n^(1/8)
    long double nd = (long double)n;
    u64 m = (u64)floor(powl(nd, 1.0L/8.0L)) + 1;

    for(u64 c = 1; ; ++c){
        auto f = [&](u64 a)->u64{
            u64 t = mul_mod(a, a, n);
            t += c;
            if(t >= n) t -= n;
            return t;
        };

        u64 y = 0;
        u64 g = 1;
        u64 q = 1;
        u64 r = 1;
        u64 k = 0;
        u64 x = 0;
        u64 ys = 0;

        while(g == 1){
            x = y;
            while(k < (3 * r) / 4){
                y = f(y);
                ++k;
            }
            while(k < r && g == 1){
                ys = y;
                u64 limit = (m < (r - k) ? m : (r - k));
                for(u64 i = 0; i < limit; ++i){
                    y = f(y);
                    u64 diff = (x > y) ? (x - y) : (y - x);
                    if(diff == 0) diff = n; // to avoid q becoming 0 in intermediate step
                    q = (u128)q * diff % n;
                }
                g = gcd_u64(q, n);
                k += m;
            }
            if(g == 0) g = 1;
            if(k >= r){
                k = r;
                r <<= 1;
            }
        }

        if(g == n){
            g = 1;
            y = ys;
            while(g == 1){
                y = f(y);
                u64 diff = (x > y) ? (x - y) : (y - x);
                g = gcd_u64(diff, n);
            }
        }
        if(g == n) continue;
        if(is_prime(g)) return g;
        if(is_prime(n / g)) return n / g;
        return find_prime_factor(g);
    }
    // unreachable
    return 1;
}

unordered_map<u64,int> factorize(u64 n){
    unordered_map<u64,int> res;
    if(n <= 1) return res;
    while(n > 1 && !is_prime(n)){
        u64 p = find_prime_factor(n);
        int s = 0;
        while(n % p == 0){
            n /= p;
            ++s;
        }
        res[p] += s;
    }
    if(n > 1){
        res[n] += 1;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q;
    if(!(cin >> Q)) return 0;
    vector<string> answers;
    for(int _ = 0; _ < Q; ++_){
        u64 N;
        cin >> N;
        auto mp = factorize(N);
        set<int> exps;
        for(auto &kv : mp) exps.insert(kv.second);

        // replicate Python behavior: for empty set, all(...) is True, so it will pick 60
        int found = 1;
        for(int i = 60; i >= 1; --i){
            bool ok = true;
            for(int x : exps){
                if(x % i != 0){
                    ok = false;
                    break;
                }
            }
            if(ok){
                answers.push_back(to_string(i));
                found = 1;
                break;
            }
        }
        // (always found because loop includes i=1)
    }

    for(size_t i = 0; i < answers.size(); ++i){
        if(i) cout << '\n';
        cout << answers[i];
    }
    cout << '\n';
    return 0;
}