結果

問題 No.1611 Minimum Multiple with Double Divisors
ユーザー lam6er
提出日時 2025-03-20 20:52:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,916 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 103,888 KB
最終ジャッジ日時 2025-03-20 20:52:55
合計ジャッジ時間 24,871 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 1 WA * 10 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
import random

def input():
    return sys.stdin.read()

def is_prime(n):
    if n < 2:
        return False
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if n % p == 0:
            return n == p
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for a in [2, 3, 5, 7, 11]:
        if a >= n:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def pollards_rho(n):
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    if n % 5 == 0:
        return 5
    while True:
        c = random.randint(1, n - 1)
        f = lambda x: (pow(x, 2, n) + c) % n
        x, y, d = 2, 2, 1
        while d == 1:
            x = f(x)
            y = f(f(y))
            d = math.gcd(abs(x - y), n)
        if d != n and is_prime(d):
            return d
        elif d != n:
            continue
        else:
            break
    return d

def factor(n):
    if n == 1:
        return []
    factors = []
    while n > 1:
        if is_prime(n):
            factors.append(n)
            break
        d = pollards_rho(n)
        if is_prime(d):
            factors.append(d)
            n //= d
        else:
            factors.extend(factor(d))
            n //= d
    return factors

def get_prime_factors(n):
    if n == 1:
        return {}
    factors_list = factor(n)
    factor_counts = {}
    for p in factors_list:
        if p in factor_counts:
            factor_counts[p] += 1
        else:
            factor_counts[p] = 1
    return factor_counts

primes_strategy1 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

def solve():
    data = sys.stdin.read().split()
    T = int(data[0])
    results = []
    for i in range(1, T + 1):
        X = int(data[i])
        if X == 1:
            results.append(2)
            continue
        factors = get_prime_factors(X)
        factors_p = set(factors.keys())
        p_strategy1 = None
        for p in primes_strategy1:
            if X % p != 0:
                p_strategy1 = p
                break
        if p_strategy1 is None:
            p_candidate = 2
            while True:
                if p_candidate not in factors_p and is_prime(p_candidate):
                    p_strategy1 = p_candidate
                    break
                p_candidate += 1
        Y1 = X * p_strategy1
        min_Y = Y1
        for p in factors:
            exponent = factors[p]
            Y_candidate = X * (p ** (exponent + 1))
            if Y_candidate < min_Y:
                min_Y = Y_candidate
        results.append(min_Y)
    print('\n'.join(map(str, results)))

if __name__ == '__main__':
    solve()
0