#1084116 (PyPy3) No.1611 Minimum Multiple with Double Divisors

• 問題: No.1611 Minimum Multiple with Double Divisors
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:19:41
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 6,968 bytes
• コンパイル時間: 280 ms
• コンパイル使用メモリ: 82,796 KB
• 実行使用メモリ: 86,656 KB
• 最終ジャッジ日時: 2025-05-14 13:20:55
• 合計ジャッジ時間: 7,980 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	-- * 2
other	AC * 1 WA * 10 TLE * 1 -- * 25

ソースコード

import sys
import math

# Function to generate primes up to n using Sieve of Eratosthenes
def get_primes(n):
    """
    Generates a list of prime numbers up to n using the Sieve of Eratosthenes.
    """
    primes = []
    is_prime = [True] * (n + 1)
    # 0 and 1 are not prime
    if n >= 0: is_prime[0] = False
    if n >= 1: is_prime[1] = False
    
    for p in range(2, n + 1):
        if is_prime[p]:
            primes.append(p)
            # Mark multiples of p as not prime. Start from p*p for optimization.
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
    return primes

# Function to find the prime factorization of a number n
# Uses the precomputed list of primes for trial division up to sqrt(n)
def get_prime_factorization_optimized(n, primes_list):
    """
    Finds the prime factorization of n using trial division with precomputed primes.
    Returns a dictionary where keys are prime factors and values are their exponents.
    """
    factors = {}
    temp_n = n
    
    idx = 0
    # Iterate through the precomputed primes list
    while idx < len(primes_list):
        p = primes_list[idx]
        
        # Optimization: If p*p > temp_n, then the current temp_n must be prime
        # because all smaller potential prime factors have already been divided out.
        # Using p > temp_n // p check to avoid potential overflow for large p, although p*p fits 64-bit for p up to ~3e9.
        # The condition p*p > temp_n is safe for p <= sqrt(10^11).
        if p * p > temp_n: 
            break
        
        # If p divides temp_n, find its exponent
        if temp_n % p == 0:
            count = 0
            while temp_n % p == 0:
                count += 1
                temp_n //= p
            factors[p] = count
        
        # Optimization: if temp_n becomes 1, factorization is complete.
        if temp_n == 1:
             break

        idx += 1 # Move to the next prime in the list

    # If temp_n > 1 after the loop, the remaining temp_n is a prime factor itself.
    # This can happen if n has a large prime factor > sqrt(n).
    if temp_n > 1:
        # Add this large prime factor to the dictionary.
        # The exponent must be 1 because if it were higher (e.g., temp_n = P^k with k>=2),
        # then P <= sqrt(temp_n), and P should have been found during the loop.
        factors[temp_n] = factors.get(temp_n, 0) + 1 
        
    return factors

# Function to find the smallest prime number that is NOT a factor of X
# factors_map contains the prime factorization of X
def find_smallest_missing_prime(factors_map, primes_list):
    """
    Finds the smallest prime from primes_list that is not a key in factors_map.
    """
    for p in primes_list:
        # The first prime encountered that is not in the keys of factors_map is the smallest missing prime.
        if p not in factors_map:
            return p
            
    # This part should theoretically not be reached for X <= 10^11.
    # The product of the first few primes grows very quickly.
    # Product of primes up to 31 exceeds 10^11.
    # So the smallest missing prime (q_min) must be <= 37.
    # The precomputed primes list extends far beyond this.
    return -1 # Should indicate an error or unexpected situation

# Main logic to solve the problem for a single test case X
def solve(primes_list): 
    """
    Solves the problem for a single value X, given the list of precomputed primes.
    Prints the minimum Y satisfying the conditions.
    """
    X = int(sys.stdin.readline())
    
    # Handle the base case X = 1 separately.
    # tau(1) = 1. We need Y with tau(Y) = 2*1 = 2.
    # Smallest number with 2 divisors is the smallest prime, 2.
    # Y must be a multiple of X=1 (always true). Minimum Y is 2.
    if X == 1:
        print(2)
        return

    # Get the prime factorization of X
    factors = get_prime_factorization_optimized(X, primes_list)
    
    # Initialize min_Y to -1, representing infinity or uninitialized state.
    min_Y = -1 

    # Explore candidates for Y based on modifying existing prime factors of X (Case 1)

    # Candidate Type 1.1: Increase the exponent of one prime factor p_j by (a_j+1).
    # Y_j = X * p_j^(a_j+1) results in Y_j = p_1^a_1 ... p_j^(a_j + (a_j+1)) ... p_k^a_k = p_1^a_1 ... p_j^(2a_j+1) ... p_k^a_k
    # tau(Y_j) = (a_1+1)...(2a_j+1+1)...(a_k+1) = (a_1+1)...(2(a_j+1))...(a_k+1) = 2 * tau(X)
    for p, a in factors.items():
        # Calculate p^(a+1). Python handles large integers.
        pk_power = pow(p, a + 1)
        # Calculate the candidate Y = X * p^(a+1)
        candidate_Y = X * pk_power
        
        # Update min_Y if this candidate is smaller than the current minimum
        if min_Y == -1 or candidate_Y < min_Y:
            min_Y = candidate_Y

    # Candidate Type 1.2 (Special Case): If X has exactly two prime factors p1, p2
    # with exponents (1, 2) or (2, 1).
    # In this case, Y = X * p1 * p2 is also a valid candidate.
    # Y = p1^(a1+1) * p2^(a2+1) * ...
    # tau(Y) = (a1+1+1)(a2+1+1)... = (a1+2)(a2+2)...
    # We need tau(Y) = 2*tau(X). This simplifies to (a1+2)(a2+2) = 2(a1+1)(a2+1).
    # This equality holds only if (a1, a2) is (1, 2) or (2, 1).
    if len(factors) == 2:
        p_list = list(factors.keys())
        p1 = p_list[0]
        p2 = p_list[1]
        a1 = factors[p1]
        a2 = factors[p2]
        # Check if exponents match the special case condition
        if (a1 == 1 and a2 == 2) or (a1 == 2 and a2 == 1):
            # Calculate the special candidate Y = X * p1 * p2
            candidate_Y = X * p1 * p2
            # Update min_Y if this candidate is smaller
            if min_Y == -1 or candidate_Y < min_Y:
                min_Y = candidate_Y

    # Explore candidates for Y based on introducing a new prime factor (Case 2)
    # We need tau(Y) = 2 * tau(X). If Y = X * q^c, tau(Y) = tau(X) * (c+1).
    # So c+1 = 2, which means c=1. Y = X * q.
    # To minimize Y, we must choose the smallest prime q (denoted q_min) that does not divide X.
    
    # Find the smallest prime q_min not in the factors of X
    q_min = find_smallest_missing_prime(factors, primes_list)
       
    # Calculate the candidate Y = X * q_min
    candidate_Y_new = X * q_min
    # Update min_Y if this candidate is smaller
    if min_Y == -1 or candidate_Y_new < min_Y:
        min_Y = candidate_Y_new
        
    # Print the overall minimum Y found across all candidates
    print(min_Y)

# === Main Execution ===

# Precompute primes up to sqrt(Maximum X value) + a small buffer.
MAX_X = 10**11
# Calculate the integer part of sqrt(10^11)
MAX_PRIME_CHECK = int(math.sqrt(MAX_X)) + 2 # A limit slightly above the square root
# Generate primes using the Sieve
primes = get_primes(MAX_PRIME_CHECK) 

# Read the number of test cases
T = int(sys.stdin.readline())
# Process each test case
for _ in range(T):
    solve(primes) # Pass the precomputed primes list to the solver function