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.
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.
Maybe a novice question but
How will we store the largest/smallest prime factor for each (A[i]<=10^9) in terms of memory?
map I guess
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 ..
You can do that for $$$A[i] \le 10^6$$$ or something using a sieve. Smallest prime divisor also works.
$$$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/
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$$$.
yep damn
What if I give you $$$A_i = $$$ unique prime, the problem here is that we need that LCM under a modulo
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.
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:
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> countwherecount[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).Yup — the pollard rho.
Asumming the time limit is $$$1$$$ second then this approach also having its large constant factor to pass it unfortunely :(
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.
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
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
No you cant calculate LCM like that for an entire array
Sad community we live in where people are downvoted for trying out different approaches on a problem.
Maybe this will help.
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).
You could get rid of
std::set, because it might slow down your program significantly. That is, keeping final results ofA[i]instd::vectorand usingstd::sortandstd::uniqueright after you've processed allA[i]is the way.In general, replacing
std::setorstd::mapwithstd::vectoroptimizes your program, but requires more implementation. However, due to existence ofstd::sortandstd::unique, the given problem is even easy to code.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.