結果
| 問題 |
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