vanwij's blog

LCM of all numbers in array
By vanwij, history, 3 years ago, In English

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.

Tags lcm
  • Vote: I like it
  • +20
  • Vote: I do not like it

Comments Comments (22)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

One way of making this faster could be to remove duplicates from the array. Another way (which I'm not too sure of in terms of getting a visible speedup) could be: rather than iterating over all $$$p$$$, factorize $$$A_i$$$ directly. While factorizing, instead of using a brute force algorithm (that iterates over all primes $$$\le \sqrt{x}$$$), you could revert to a sieve based algorithm which stores the largest prime factor of the number after the number becomes small enough. Before this, it would probably also be better to do a Miller Rabin test to check for primality to avoid the worst case. If the bottleneck is the divisions, you can maintain $$$\pi(M)$$$ Barrett reduction structs for divisibility testing, and taking mods for $$$10^9 + 7$$$ (maybe even using Montgomery multiplication) should be easy to optimize as well.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Maybe a novice question but

    How will we store the largest/smallest prime factor for each (A[i]<=10^9) in terms of memory?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      map I guess

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If we are using sieve for smallest prime factor, i guess it would require to store it for each (1-Amax) .. that's how I have generally used it Prime Factorisation using sieve

        and if not using sieve, just using generic sqrt(A) prime factorisation that would still lead to worst case (N*sqrt(A)) complexity ..

        → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You can do that for $$$A[i] \le 10^6$$$ or something using a sieve. Smallest prime divisor also works.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -54 Vote: I do not like it

$$$LCM(A_1,A_2,A_3,...,A_n) = LCM(LCM(A_1,A_2,A_3,...,A_{n-1}),A_N)$$$

https://www.geeksforgeeks.org/lcm-of-given-array-elements/

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    This doesn't work if you reduce the intermediate results modulo something. For example, consider $$$[A_1, A_2, A_3] = [10^6, 10^6 + 1, 10^6]$$$, with the modulus as $$$10^9 + 7$$$.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    What if I give you $$$A_i = $$$ unique prime, the problem here is that we need that LCM under a modulo

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

You can find the prime factors of a number in O(n^1/4) where n is a[i]. So, it would be something like 177 * |a|. Then you might be able to use your set approach.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    I assume you're talking about the Pollard-Rho algorithm.

    We can use this to factorize all $$$A_i$$$ in $$$\displaystyle{\mathcal{O}\left(N\log{A_i}\sqrt[4]{A_i}\right) \approx 53.1\cdot10^6}$$$ operations. Note that the $$$\log A_i$$$ factor comes from using $$$\textrm{gcd}$$$.

    Notice that there are at most $$$\log_2A_i$$$ factors of any $$$A_i$$$. That means there are at most $$$N\log_2(10^9) \approx 30N \leq 3\cdot10^5$$$ total factors, so looping over them fits comfortably in the TL.

    Now we can use an alternate definition of $$$\textrm{lcm}$$$ based off of prime factors:

    $$$\textrm{lcm}(A_1,A_2,\dots) = p_1^{e_1}p_2^{e_2}\dots$$$

    where $p$ is a set of all distinct prime factors of any $$$A_i$$$, and $$$e_i$$$ stores the largest power of $$$p_i$$$ that divides any $$$A_i$$$.

    Now, use map<int, int> count where count[p] stores the largest power of $$$p$$$ that divides any $$$A_i$$$.

    Now, just calculate the product on the right modulo $$$M$$$, and that's your answer.

    If you want a completely unnecessary speed boost, use binary exponentiation instead of repeated multiplication.

    Time complexity: $$$\mathcal{O}\left(N\log{A_i}\sqrt[4]{A_i} + N\log A_i\right) \approx 53.5\cdot10^6$$$ operations (assuming you use an $$$\mathcal O(1)$$$ unordered_map).

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Yup — the pollard rho.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Asumming the time limit is $$$1$$$ second then this approach also having its large constant factor to pass it unfortunely :(

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Does pollard-rho has that big of constant factor ? If so, then how does it compare to the naive $$$O(\sqrt{N})$$$ trial division, for factoring a number up to 1e9 in contest environment ? Thanks.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes due to many modulo operations (though there are ways that you can optimize furthur), but combining with precalculation and sieving upto $$$10^6$$$ can give you a boost

          → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

what if we multiply all of them modulo 1000000007 and then multiply by the inverse element in the ring modulo GCD (A1, AN). ((A1*A2*...*AN) % 1000000007 * (GCD(A1, AN)^(1000000007 — 2) % 1000000007) % 1000000007

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No you cant calculate LCM like that for an entire array

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Sad community we live in where people are downvoted for trying out different approaches on a problem.

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Maybe this will help.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I see no problem here, maybe you should specify time limits? Cause for this constraint : $$$1≤N≤10^4$$$, $$$1≤Ai≤10^9$$$ almost naive approach with all primes generation up to 32K (3432 prime numbers) takes less then 0.5 sec with ~ O(N*3K).

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

You could get rid of std::set, because it might slow down your program significantly. That is, keeping final results of A[i] in std::vector and using std::sort and std::unique right after you've processed all A[i] is the way.

In general, replacing std::set or std::map with std::vector optimizes your program, but requires more implementation. However, due to existence of std::sort and std::unique, the given problem is even easy to code.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you everyone for the ideas and explanations. I am not really sure whether the constraint for $$$N$$$ was 1e4 or 1e5 on the original problem, but anyway I learnt a lot from the discussion.

→ Reply