Skills101
← All coding problems

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: n integers a₁ … 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).

Loading editor…

Log in to run and submit your code — it's free.