結果

問題 No.1611 Minimum Multiple with Double Divisors
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:44:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,011 bytes
コンパイル時間 152 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 99,704 KB
最終ジャッジ日時 2025-06-12 16:44:33
合計ジャッジ時間 9,825 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 1 WA * 10 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def sieve(max_limit):
    sieve = [True] * (max_limit + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(math.sqrt(max_limit)) + 1):
        if sieve[i]:
            for j in range(i*i, max_limit+1, i):
                sieve[j] = False
    primes = []
    for i in range(2, max_limit + 1):
        if sieve[i]:
            primes.append(i)
    return primes

# Generate a list of primes up to 1e5
primes = sieve(10**5)

def factorize(x):
    factors = {}
    i = 0
    while i < len(primes) and primes[i] * primes[i] <= x:
        p = primes[i]
        while x % p == 0:
            factors[p] = factors.get(p, 0) + 1
            x = x // p
        i += 1
    if x > 1:
        factors[x] = 1
    return factors

def find_p_min(factors):
    for p in primes:
        if p not in factors:
            return p
    # If all primes in list are factors, return next prime
    # This is a simplification; in reality, we'd need to find the next prime beyond the list
    return primes[-1] + 2  # This is incorrect but for the sake of example

def main():
    input = sys.stdin.read().split()
    T = int(input[0])
    cases = list(map(int, input[1:T+1]))
    for X in cases:
        if X == 1:
            print(2)
            continue
        factors = factorize(X)
        min_case_b = None
        # Check if any exponent is odd
        has_odd = any(a % 2 == 1 for a in factors.values())
        if has_odd:
            for p, a in factors.items():
                if a % 2 == 1:
                    delta = a + 1
                    y_candidate = X * (p ** delta)
                    if min_case_b is None or y_candidate < min_case_b:
                        min_case_b = y_candidate
        # Compute case a
        p_min = find_p_min(factors)
        y_a = X * p_min
        if has_odd:
            if min_case_b < y_a:
                print(min_case_b)
            else:
                print(y_a)
        else:
            print(y_a)

if __name__ == "__main__":
    main()
0