### vanwij's blog

By vanwij, history, 4 weeks ago,

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.

• +20

 » 4 weeks ago, # | ← Rev. 2 →   +23 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.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 Maybe a novice question but How will we store the largest/smallest prime factor for each (A[i]<=10^9) in terms of memory?
•  » » » 4 weeks ago, # ^ |   0 map I guess
•  » » » » 4 weeks ago, # ^ |   0 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 ..
•  » » » 4 weeks ago, # ^ |   +3 You can do that for $A[i] \le 10^6$ or something using a sieve. Smallest prime divisor also works.
 » 4 weeks ago, # | ← Rev. 2 →   -54 $LCM(A_1,A_2,A_3,...,A_n) = LCM(LCM(A_1,A_2,A_3,...,A_{n-1}),A_N)$
•  » » 4 weeks ago, # ^ |   +32 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$.
•  » » » 4 weeks ago, # ^ |   +3 yep damn
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 What if I give you $A_i =$ unique prime, the problem here is that we need that LCM under a modulo
 » 4 weeks ago, # | ← Rev. 2 →   +8 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.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 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 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).
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 Yup — the pollard rho.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Asumming the time limit is $1$ second then this approach also having its large constant factor to pass it unfortunely :(
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 4 weeks ago, # ^ |   0 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
 » 4 weeks ago, # | ← Rev. 2 →   0 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
•  » » 4 weeks ago, # ^ |   0 No you cant calculate LCM like that for an entire array
•  » » 4 weeks ago, # ^ |   +3 Sad community we live in where people are downvoted for trying out different approaches on a problem.
 » 4 weeks ago, # |   +3 Maybe this will help.
•  » » 4 weeks ago, # ^ |   0 sap nigga
 » 4 weeks ago, # | ← Rev. 3 →   0 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).
 » 4 weeks ago, # | ← Rev. 2 →   0 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.
 » 4 weeks ago, # |   +13 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.
 » 4 weeks ago, # |   0 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.
 » 3 weeks ago, # |   0 I used integer factorization . Here is my code . Code #include"bits/stdc++.h" using namespace std; #define Fast_D cout<>ws; getline(cin,s); #define ff first #define ss second #define Local 0 #if (Local == 1) #define debug(x) cout << __LINE__ << " " << #x <<"..." << x << endl; #endif const double PI = 3.141592653589793; const int mod = 1e9 + 7; int power(int a, int b) { int res = 1; while(b) { if(b&1) { res *= a ; res %= mod ; } a *= a; a %= mod ; b >>= 1 ; } return res ; } void PlayGround() { int n; cin >> n; int a[n]; for(int i=0;i> a[i] ; } set s; map mp ; for(int i=0;i