LCM of all numbers in array

Revision en1, by vanwij, 2021-09-27 16:29:40

Hello ! I have a problem that goes :

Given $N$ positive integers $A_1, A_2, \dots, A_N$. Find $LCM(A_1, A_2, \dots, A_N)\text{ }(\text{mod } 1000000007)$.

Constraint : $1\leq N \leq 10^4,$ $1\leq A_i \leq 10^9$

My approach :

Use sieve to list all primes up to $M = \sqrt{A_{max}}$. For every prime $p$ up to $M$, divide each $A_i$ by $p$ as many time as possible (as long as $A_i$ is divisible by $p$), and note the largest exponent for each $p$.

After every $A_i$ is 'reduced' (divided by all prime up to $M$), $A_i$ must be equal to $1$ or a prime greater than $M$. Note every distinct final result of $A_i$. This was done using std::set.

To calculate $LCM(A_1, A_2, \dots, A_N)$, I used binary exponentiation to calculate the 'contribution' for every small prime $p \leq M$, and then multiply them with the 'contribution' for large prime, which is equal to the product of all distinct final result of $A_i$ 's.

However, this approach yields TLE and I cannot figure out a faster way to solve the problem. Any ideas to solve the problem and explanations are appreciated. Thanks in advance.

This problem is from simulation phase of a contest I joined. Both the simulation and the contest itself was over by September 25th, 2021.

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 vanwij 2021-09-27 16:29:40 1287 Initial revision (published)