vanwij's blog

By vanwij, history, 3 weeks 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

»
3 weeks 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.

  • »
    »
    3 weeks 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?

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

      map I guess

      • »
        »
        »
        »
        3 weeks 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 ..

    • »
      »
      »
      3 weeks 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.

»
3 weeks 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/

  • »
    »
    3 weeks 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$$$.

  • »
    »
    3 weeks 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

»
3 weeks 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.

  • »
    »
    3 weeks 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).

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      Yup — the pollard rho.

    • »
      »
      »
      3 weeks 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 :(

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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

»
3 weeks 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

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

    No you cant calculate LCM like that for an entire array

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Maybe this will help.

»
3 weeks 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).

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think the following might be a possible optimization : When we try to find the largest power of small prime $$$p$$$ then we can do binary search on the power of the prime in the range [1,pmax] where pmax is the maximum power of prime p that can be contained in the range $$$[1, 10^9] $$$, for example 2 will have pmax 30. For each iteration of the binary search we need to check if there exists any number in the array which is divisble by that power of p.

»
3 weeks 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.

»
3 weeks 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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I used integer factorization . Here is my code .

Code