can any body explain the SEALCM editorial in detail . i am not able to grasp the approach properly. please help . here is the link for the editorial – SEALCM - Editorial - editorial - CodeChef Discuss
1 Like
The problem an be solved in two ways:
1 - Dp (explained in editorial)
2 - Set Theory( the one I used)
I will explain my solution.
First of all as you can see the limit of m is 1000, then the max number of distinct prime factors it can have is 4 (2 X 3 X 5 X 7 X 11>1000), which is quite low.
Now as per the question we have to find the number of array whose lcm is a multiple of a given number(say x).
I used the negation of this i.e. you can calculate number of arrays whose lcm is not multiple of x(let’s say we get ans as y).
Hence, ans = (no of arrays that can be formed of size n ) - (y)
Now to calculate y.
First understand that lcm is calculated by taking each prime factor present in the elements of the array to it’s highest power present.
So we first factorize x into it’s prime factors. Now let x be of the form x= (a^b)(c^d)(e^f)*(g^h).
Now keep the factors in the form of A=(a^b),B=(c^d),C=(e^f),D=(g^h).
First of all to calculate y, there are few requirements.
Either none of the elements of the array have any prime factor that x has OR it may have some of it missing.
Now set theory has a principle of union, which I used.
n(X U Y)= n(X) + n(Y) - n(X intersection Y). where U = union
So y = n(NOT(A) U NOT(B) U NOT(C) U NOT(D)).
This statements practically means that I want to calculate number of arrays such that either (A or it’s multiples are not present ) or (B or it’s multiples are not present) or (C or it’s multiples are not present) or (D or it’s multiples are not present).
Using the [Inclusion-Exclusion Principle][1], I calculated y.
As you will see the complexity of it is O(2^n), which works as our n depends on number of components ,like A, that are present in the number which is at most 4, as proved above.
Now you just have to learn implementing Inclusion-Exclusion Principle and deMorgan’s Law to calculate negation.
If you understand the concept, rest would be easy.
[1]: Inclusion–exclusion principle - Wikipedia
5 Likes
Hi @thechamp103,
I am not able to understand your uni function 
as well as lines 77-88.
Clearly,I have not implemented inclusion exclusion principle yet.
Could you please guide me?? 