### Mikemirzyanov1's blog

By Mikemirzyanov1, history, 6 months ago,

This is the problem from today's codechef challenge.

problem

Can someone tell me what am I doing wrong as I have seen the code of lot of people and I am also doing the same thing as they have done.Also I have tried some test cases and they indeed give correct answer.

• -6

 » 6 months ago, # |   +8 power is not reset between test cases.
•  » » 6 months ago, # ^ |   +4 can u explain me the logic for this problem
•  » » » 6 months ago, # ^ |   +11 The idea is to try all values of the new element (from $1$ to $M$) and take the maximum LCM it gives you. Naively, this is $O(T(N + M)\log(M))$ (extra log because we need GCD for LCM), which passes fine. The issue is, the LCM could be huge, so we need to do it without overflowing.Instead, let's represent the LCM as the prime factors that make it up, e.g. $12$ becomes $2 \cdot 2 \cdot 3$. Now consider each prime factor individually. In terms of each prime factor $p$, for each element in the array, the LCM must be big enough to be a multiple of all of them. Formally, if each array element is $p^k \cdot something$, then the LCM must be divisible by $p^m$, where $m$ is the maximum over all $k$ of all array elements. If we do this for each prime factor of the array elements, we'll have the LCM.Now we handle the new element. Let's call it... $G$ (this is also how I come up with variable names). What does a candidate $G$ contribute to the LCM? Since the LCM is the product of $p^m$ for all valid $p$, we only care about the prime factors of $G$ where we can somehow increase some values of $m$. Specifically, for all prime factors $p$ of $G$, if $G$ is divisible by $p^k$ and the LCM is divisible by $p^m$, then we increase the LCM only if $k > m$, and we increase the LCM by $p^{k - m}$. So the final contribution is $\prod{p^{\max(0, k - m)}}$ for all prime factors $p$ of $G$.Try this for all $G$ from $1$ to $M$, and you're done. This is, as an upper bound, still $O(T(N + M)\log(M))$ because each number can have around $log(M)$ prime factors, but it won't run close to this practically. To get this complexity, precompute prime factors for each number at the beginning (this can be done, say, in $O(10000\sqrt {10000})$). The only issue with the solution above was that it didn't reset the max counts between test cases.I appreciate you asking, because by explaining the problem, I've come to think of LCM in a different way.
•  » » » » 6 months ago, # ^ |   0 My logic is that a number can only increase the LCM if there is no such number in the given array which is a factor of that number. I will use a boolean array, say BIT[m+1] where the i index is 1 if the number i is present in the given array and zero if not(ignore the 0 index). Then I will run a loop from i = m to i = 1 and check if bit[m] == 1 and check if any number from the given array is a factor of that number. If we get such a number, we break the loop and the first number that satisfies the condition will maximize the LCM.https://www.codechef.com/viewsolution/30850090This is my solution please check what is wrong in my code
•  » » » » » 6 months ago, # ^ |   0 I'll give you a countercase, you can figure out why your program is incorrect: 1 2 4 2 3 expected answer: 4, your answer: 1
•  » » 6 months ago, # ^ |   0 Oh man thankyou so much. Almost spent 3 hours fixing other things XD.
 » 6 months ago, # |   +22 are you from headquaters1
•  » » 6 months ago, # ^ |   +15 No I'm second in command from headquarter itself. It's just that Mike handles everything by himself XD.