結果

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

ソースコード

diff # 

import sys
import math

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(math.isqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

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

def find_q(primes_in_x):
    q = 2
    while True:
        if q not in primes_in_x:
            if is_prime(q):
                return q
        if q == 2:
            q += 1
        else:
            q += 2

def solve():
    input = sys.stdin.read().split()
    T = int(input[0])
    for i in range(1, T+1):
        X = int(input[i])
        if X == 1:
            print(2)
            continue
        factors = factorize(X)
        primes = list(factors.keys())
        primes_set = set(primes)
        s_list = [factors[p] + 1 for p in primes]
        # Compute Y1
        q = find_q(primes_set)
        Y1 = X * q
        # Compute Y2_candidates
        min_Y2 = float('inf')
        for p, s in zip(primes, s_list):
            Y2_candidate = X * (p ** s)
            if Y2_candidate < min_Y2:
                min_Y2 = Y2_candidate
        if primes:
            answer = min(Y1, min_Y2)
        else:
            answer = Y1
        print(answer)

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