LCM of an Array (Modulo 10^9+7)
mediumMath & Number Theory+20 XPTime limit 3s
n traffic signals turn green every a₁, a₂, …, aₙ seconds. They all turned green together at time 0; they will next all be green together after LCM(a₁, …, aₙ) seconds. That number can be astronomically large, so print it modulo 1000000007.
Input:
- line 1:
n - line 2:
nintegersa₁ … aₙ
Output: LCM(a₁, …, aₙ) mod 1000000007.
Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ aᵢ ≤ 10⁶.
Think about it: you can't take the modulus in the middle of lcm = lcm · x / gcd(lcm, x) — division doesn't survive a modulus. Instead, factorise every number (a smallest-prime-factor sieve helps) and keep the highest power of each prime seen. The LCM is the product of those prime powers, which you can multiply modulo p.
Sample input 1
3 4 6 10
Sample output 1
60
Sample input 2
4 1 1 1 1
Sample output 2
1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).