求解数组所有元素的最小可整除完全平方数的模10^9+7值（大数场景）

Got it, let's work through this problem together. We need to find the smallest perfect square that's divisible by every element in the array, then compute that square modulo 10^9 + 7—and we have to do this efficiently even when the array has up to 1e5 elements, each as big as 1e7.

First, let's break down what the smallest such square needs to satisfy:

• It must be divisible by every element in the array, which means for every prime factor present in any element, the square's exponent for that prime has to be at least the maximum exponent of that prime across all elements (this is essentially the prime factorization of the array's LCM).
• Since it's a perfect square, every prime's exponent must be even. So we'll adjust each maximum exponent to the smallest even number that's greater than or equal to it (add 1 if it's odd, leave it as-is if even).
• Multiply all these primes raised to their adjusted exponents, then take modulo 10^9 +7 to get our answer.

1. Precompute Smallest Prime Factors (SPF) #

To factorize numbers up to 1e7 quickly, we'll use a sieve-based approach to precompute the smallest prime factor for every number up to 1e7. This lets us factorize any number in O(log x) time later on.

MOD = 10**9 + 7
MAX_A = 10**7

# Precompute smallest prime factor for each number up to MAX_A
spf = list(range(MAX_A + 1))
for i in range(2, int(MAX_A**0.5) + 1):
    if spf[i] == i:  # i is a prime number
        for j in range(i*i, MAX_A + 1, i):
            if spf[j] == j:
                spf[j] = i

2. Track Maximum Exponents for Each Prime #

Next, we'll go through each element in the array, factorize it using our SPF array, and keep track of the highest exponent we see for each prime.

from collections import defaultdict

def factorize(x):
    factors = defaultdict(int)
    while x != 1:
        prime = spf[x]
        while x % prime == 0:
            factors[prime] += 1
            x = x // prime
    return factors

max_exponents = defaultdict(int)
# Assume A is our input array
for num in A:
    if num == 1:
        continue  # 1 has no prime factors, doesn't affect our result
    prime_counts = factorize(num)
    for p, cnt in prime_counts.items():
        if cnt > max_exponents[p]:
            max_exponents[p] = cnt

3. Calculate the Result Modulo 10^9 +7 #

Now we adjust each exponent to be even, then compute the product of each prime raised to its adjusted exponent—using modular exponentiation to keep numbers manageable and avoid overflow.

def modular_pow(base, exp, mod):
    result = 1
    base = base % mod
    while exp > 0:
        # If exponent is odd, multiply result by base
        if exp % 2 == 1:
            result = (result * base) % mod
        # Square the base and halve the exponent
        base = (base * base) % mod
        exp = exp // 2
    return result

result = 1
for prime, cnt in max_exponents.items():
    # Adjust to the smallest even number >= cnt
    adjusted_exp = cnt if cnt % 2 == 0 else cnt + 1
    result = (result * modular_pow(prime, adjusted_exp, MOD)) % MOD

print(result)

• Deduplicate the array: If there are duplicate elements, we can convert the array to a set first to avoid redundant factorizations—this saves time for arrays with lots of repeats.
• Memory considerations: The SPF array for 1e7 takes about 40MB (since each integer in Python is ~4 bytes), which is totally manageable on modern systems.
• Edge case: All 1s: If every element is 1, the smallest perfect square is 1, so the result is 1 mod 10^9+7 = 1.
• Assumptions: We're assuming all array elements are positive integers (since divisibility by 0 is undefined, the problem likely implies this).

内容的提问来源于stack exchange，提问作者Nguyễn Vũ Minh