MXMLCM - Editorial

what wrong with my code? it gives WA

@taran_1407 won’t the complexity of your code be O( (N + M) * log(M)) ? because while processing N values and M values, you are using the exact same logic.

Can anyone help me with my code β†’ It gave WA on second task of subtask2 , rest all are passed. there might be very small edge case mistake , i am not abe to figure out.
My Code

I used smallest prime factor of a number for prime factorization.

@tushar_18030 I have highlighted the correction in the code here.
The problem was in the formulae which counted the change contributed by a number.

Hope this helped :slightly_smiling_face:

1 Like

Thank u so much :slight_smile:

@anon70769165 calculating the LCM from the prime factorization will overflow even the range of long long int (also mentioned in the editorial). Whole motive of calculating the prime factorization of LCM was to use it to calculate the change contributed by i (1 <= i <= M) to the LCM
see this video to know how to calculate the change contributed by i

@anon14510829 I have highlighted the change as to why the powers of prime factorizations were incorrect in this code.

But still it needed to be further optimized to pass the test case as creating a new map for each iteration where a single variable can be used is really redundant and slow.

@jerry_storm here, the optimized version of your code.
Actually again and initializing temp[] for each n values was taking too much time.