I stared at DP and LCM. It stared back.

追加: 2026-05-30

[00:00:00]In this video, we will talk about dynamic programming on LCM.

[00:00:05]This is a very common and standard technique in the world of competitive programming, especially on CodeChef and Codeforces.

[00:00:15]But I just realized that whatever tricks we call as standard, that might not actually be standard if you are someone who is new to the world of competitive programming.

[00:00:29]So, every standard technique, even something as small as prefix sum, must have been something that is completely unknown to you.

[00:00:40]So, that is why I'm creating this video so that you you get awareness about such standard tricks out there. Now, play pay close attention to what I uh talk about in this video, because some of these facts that I state, that might seem very obvious to some of you and absolutely baffling to others.

[00:01:06]So, it all depends upon how well you understand your dynamic programming and number theory.

[00:01:13]So, the problem that we will discuss is this simple problem that for each L from 1 up to 10 to the power 6, find out how many pairs exist such that the LCM of these two numbers is equal to L.

[00:01:35]Now, notice that in this first iteration, they have not specified the constraints on X and Y, but this is the first standard observation that you can make, that they don't actually need to specify the constraints of X and Y, because one thing is for sure that LCM of X and Y is greater than X and also greater than or equal to Y.

[00:02:09]This means that if they have just specified L, it is apparent that X and Y, both the elements of the pair should be less than or equal to L.

[00:02:22]But as a corollary, you can also solve the second problem that you see on the screen, which says that how many pairs have LCM greater than L.

[00:02:35]And this is the problem that appeared in a Codeforces in a CodeChef round recently.

[00:02:41]And now you see that this time they do have to specify the constraints on the uh integers X and Y. So, the constraints were specified as X should be less than equal to L and Y should be less than equal to L. But you can already see that if you are able to solve this problem, this version, the first version, then the second version is very trivial. The second version is simply L squared minus summation of the first L prefix value.

[00:03:19]So, if if your LCM is greater than L, it means that the bad pairs are basically the ones where LCM is less than or equal to L. It means the LCM is equal to 1 2 3 up to L.

[00:03:33]So, with this algorithm, you can compute all of these values. You can sum it up, and then you can subtract it from L squared, and you would get your answer.

[00:03:43]So, that is why in this video, we will not for focus too much on the second problem. Instead, our goal would be on the simplified problem which says given an LCM, how many pairs achieve this?

[00:03:59]Now, how do you solve this problem?

[00:04:02]There are actually multiple ways to solve this problem. In fact, there is a way that doesn't even involve dynamic programming.

[00:04:09]But in this video, I specifically want to talk about the dynamic programming approach because that is something new that you can actually utilize in other problems.

[00:04:21]And that is the goal for this video.

[00:04:25]Now, let's see how well do you know your LCMs. So, if I ask you, what is the LCM of two and three?

[00:04:34]It's six.

[00:04:36]What is the LCM of six and five?

[00:04:39]You will say it is 30.

[00:04:41]What is the LCM of seven and three?

[00:04:44]It is 21.

[00:04:46]Uh let's make it harder. What is the LCM of nine and five?

[00:04:52]It is actually 45.

[00:04:55]What is the LCM of six and four?

[00:04:57]It should be 24.

[00:05:00]But now, let's pause here for a bit. Is the LCM of six and four actually 24?

[00:05:08]Because when you go in this pattern, it seems that LCM most of the times is usually just the product of these numbers. So, that's why for some of you, your brain might instinctively respond and say that the LCM of six and four is equal to 24.

[00:05:28]But you know that it's not true. If you do the actual computation, the LCM of six and four is equal to 12. It is not equal to 24.

[00:05:44]But how wrong are we if we do actually say that LCM of 6 and 4 is equal to 24?

[00:05:54]Are we completely wrong or maybe a little bit wrong? Because that would dictate how you develop the algorithm not just for this problem that deals with dynamic programming on the LCM.

[00:06:10]But this product intuition that you have is actually almost correct. So you just think in your mind that the LCM of two numbers is equal to x into y.

[00:06:21]It is almost correct. There is just one small caveat and that small caveat is what is used in the harder version of this problem where the constraints are up to 10 to the power 9.

[00:06:34]And in this hard version we use this same intuitive thing that our brain just did that the LCM of two number is equal to product of them. But this only holds in some special scenarios. What are the special scenarios that I will not cover in this video? And how to actually solve that 10 to the power 9 version that I also I would not cover in this video.

[00:06:58]But in this video let us try to focus on this fact that when we say that the LCM of 6 and 4 is equal to 24, how wrong are we? Are we completely wrong or are we a little bit wrong? And what can we actually derive and what can we actually conclude from this intuition that LCM of 4 and 6 is equal to 24?

[00:07:25]So you can see that why did 24 sound intuitive? Because you just tried to multiply 4 and 6.

[00:07:36]So you can see that 4 and 6 if you just do the multiplication, then you can see that four and six multiplied together, they produce 24.

[00:07:50]So, 24 is indeed a common multiple. It is not just the lowest common multiple because the definition of LCM is lowest common multiple.

[00:08:04]So, you can see that 24 is indeed a common multiple. So, if your brain thought that LCM of four and six is 24, it is not entirely wrong.

[00:08:16]But then, what is the connection between 24 versus what the actual LCM is?

[00:08:26]So, the actual LCM is 12.

[00:08:30]And your brain just produced 24.

[00:08:34]So, can you see what is the connection between them?

[00:08:39]You can immediately notice that 12 is equal to uh 24 is equal to 12 into two.

[00:08:53]This means that 12 was the lowest uh common multiple and 24 was also a multiple.

[00:09:03]So, one obvious thing that you can conclude from this is this fact that all the common multiples are actually divisible by the lowest common multiple.

[00:09:19]Now, we are entering the territory where I'll state a couple of facts. And as I already told you before that it might be trivial to some and baffling to others. So, the statement that you see on the screen, it's actually not very obvious unless you think deeply about it. So, we are saying that all the common multiples, they are actually divisible by the lowest common multiple.

[00:09:47]This means that if your brain thought that the LCM of 4 and 6 is 24, it is not wrong, not that much wrong. In fact, even if you end up thinking that LCM of 4 and 6 is equal to 48, even then you are also not wrong. But, if you think it is 40, then you are completely wrong.

[00:10:06]So, you can generalize it and you can say that if you start thinking of of LCM as this part, uh let's see. If you So, if your brain thinks that your LCM of 4 and 6 is equal to 12, of course, it is correct. But, if it thinks it is 24, then also no big deal as such. It can also think it is 36 and 48 and 60. So, you can see that all the common multiples of 4 and 6 are exactly this 12, 24, 36, 48, and 60. And now you can see the proof of this fact in action. So, this how did we arrive at 12, 24, 36, 48, and 60? Because you have this lowest common multiple and you multiply it by two, that is how you get the second lowest common multiple. And then you multiply it by three, that is how you get by third lowest multiple and so on. So, in fact, this statement is true that all the common multiples, they are indeed divisible by the lowest common multiple.

[00:11:16]So, till now we have seen that saying that LCM of 4 and 6 is equal to any of these numbers is not entirely wrong because it already hides some information. What is the information that it hides? because if you claim that I am claiming that my answer is almost correct and my claim is that LCM is 48.

[00:11:41]So, I can conclude something concrete from this.

[00:11:44]What can I conclude? I can conclude that the actual answer is a divisor of this.

[00:11:52]Why? Because this is a multiple of this.

[00:11:54]So, keep this fact in mind. We will come back to it later.

[00:11:59]Uh what is this fact? That this 4 and 6 it has it actually has a connection not just to 12, but all the multiples of 12. And all the multiples of 12 are exactly the lowest common multiple.

[00:12:14]So, all the common multiples of 4 and 6 are the multiples of the lowest common multiples. So, you see it's a it's going in a circle when I say that all the multiples all the common multiples of 4 4 and 6, they are actually the multiples of the lowest common multiples.

[00:12:33]So, these are some of the facts that you have to be very familiar with if you want to solve problems related to LCM and GCD.

[00:12:45]So, now let's move on to the next fact.

[00:12:48]Now, if I say that LCM is a multiple of X, if you compute this LCM of X and Y.

[00:13:01]So, I claim that if LCM of X and Y is equal to L, then I my claim is that L is actually a multiple of X. So, L would be equal to either X or 2X or 3X and so on.

[00:13:18]Now, take a minute to pause this video and think about how you can prove this.

[00:13:25]Did you get the proof?

[00:13:27]So, in fact some of you might not be able to get this proof, but actually it is right there in the definition. What does the definition says? Definition literally says it is lowest common multiple.

[00:13:44]So, common multiple literally says that the multiple of X, which is X, 2X, 3X, 4X, and so on. And LCM of Y, which is Y, 2Y, 3Y, 4Y, etc. And then you find out what is the thing that is common and what is the first thing that is common, and that you call it as LCM. So, by definition LCM of X and Y is equal is a multiple of X and also a multiple of Y.

[00:14:14]So, it is Now, it is obvious if you think about it. Okay? Now, let's go on to the second fact. So, the second fact that let's consider any number >> [clears throat] >> X and Y and suppose that their LCM of X and Y is equal to L.

[00:14:34]Now, I'm claiming that X is a divisor of L and Y is also a divisor of L.

[00:14:44]Now, this is not clear from the definition, of course, right?

[00:14:48]And uh how do you prove this?

[00:14:52]Now, now if you look at this fact one So, fact one might be immediately clear to some of you, but this might not be obvious, like why is this fact true?

[00:15:02]That why is X a divisor is guaranteed to be a divisor of LCM.

[00:15:10]So, this is true because if you really understand your multiples and divisors, you will know that multiples and divisors, they are siblings.

[00:15:22]That is if X is a multiple of Y, then Y naturally is a divisor of X. So, you can see that fact two at first glance does not look obvious, but it is actually a corollary of fact one. Because in fact one we said that LCM is a multiple of X. This means X is already a divisor of multiple and Y is already a divisor of the multiple.

[00:15:55]So, using this reasoning, you can say that X and Y they are indeed divisors of L.

[00:16:05]So, this is of course a necessary condition.

[00:16:09]Now Now you know that Now, if I give you any random number 23 or like let's say 286 and I tell you, "Okay, can you tell me about numbers that have their LCM equal to 286?"

[00:16:27]Now, you can see that you can claim with kind of confidence that, "Okay, these numbers have to be divisors of 286. That is for sure. They have to be divisor pair. Like X has to be a divisor of 286, Y has to be a divisor of 286. X and Y could be equal, but both of them has to be a divisor.

[00:16:51]But now, just like what we did earlier, like we claimed something that was not obviously correct, but almost. Like we claimed that LCM of 4 and 6 is equal to 24.

[00:17:03]What happens if I claim that all the divisor pair will have LCM equal to 286?

[00:17:11]Is that correct?

[00:17:13]So, this time I want to ask the question, like how wrong is it to say that if I have a number L, I know for sure that LCM I know for sure that X and Y, they are divisors of this LCM. If they want to achieve this LCM, then they have to be the divisor. But can I also say it the other way around? That is, if I pick any two random divisor and if I pair them up, will I get LCM equal to L?

[00:17:49]How correct is it? Or how wrong is it?

[00:17:54]So, you can see that we are claiming it both ways, right? We are saying that first we have to prove that if X and Y are divisors, if X and Y have LCM equal to L, then they indeed have to be divisors, which we have already done from this fact, right? That X and X and Y, they are indeed the divisors for LCM. So, that's why in one direction we have already proved that if their LCM is equal to L, then of course they have to appear as a divisor pair.

[00:18:32]Because if they are not appearing as a divisor, if X is not appearing as a divisor in L, then X their LCM could never be equal to L.

[00:18:45]But now you will notice that not all pairs that appears at as a divisor, so so suppose it has total number of divisors as D. There are D divisors in total.

[00:19:00]So, how many pairs can you create? That is equal to D into D.

[00:19:05]Because you can use that same divisor twice.

[00:19:10]And this is the fancy thing about LCM. Because if you think about four and six you in your mind you created a 24 which is equal to 4 into 6. So you you were trying to make this divisor and this divisor separate and then you were trying to create your LCM. But now see what happens when the actual LCM is equal to 12.

[00:19:38]So if the actual LCM is equal to 12, you will notice that 12 cannot be written as 4 into 6 at the same time.

[00:19:48]So that is the beauty of LCM that you have to do it one at a time. That is you write it as 4 into 3, but 4 appeared.

[00:19:57]That's good. And then you write it as 6 into 2. And now you can notice that 6 appeared which is good.

[00:20:04]So that is why there is overlap between them.

[00:20:08]So it is perfectly fine for you to reuse the divisors. So you can see that we reused this two, right? And then we created this three. We borrowed a two from here and then we created six over here.

[00:20:23]So that's why if this L has D divisors, then you can freely place all the D entries in the first place for X and you can also freely place all the D entries for Y. So there are D squared possibilities for the possible pairs of divisors.

[00:20:45]Now we know for sure that some of the pairs whose LCM is guaranteed to be equal to X whose LCM is guaranteed to be equal to L, they will indeed appear in in this divisor pair. That we know for sure. But you will now notice that there are also some imposters lying inside of it.

[00:21:08]Because not all divisor pairs will achieve the LCM equal to X. And I will show you an example why that is true.

[00:21:17]We'll consider the same example, 24.

[00:21:22]Let's consider the same example, 24. And you know that 4 is a divisor of 24, but 6 is also a divisor of 24.

[00:21:33]Right? Both of them are are a divisor of 24, but are But do we have LCM of 4 and 6 is equal to 24? No.

[00:21:41]Right? So, this 4,6 pair is a imposter that is lying inside that D cross D uh selection that you have just made.

[00:21:55]But when we say that these imposters there are some imposters lying, and when we talk about this this fact that how wrong are we, it turns out that we are actually not that wrong in claiming that all the divisor pairs uh that all the divisor pair will have LCM L. We are not that wrong in claiming this. So, now next we will explore what do the actual LCM of these imposters look like.

[00:22:32]Now, from your intuition, what do you think the actual LCM of these imposters look like?

[00:22:39]So, with this example that I've just given you, and with the fact that I shared with you earlier, that all the common multiples are actually multiples of the lowest common multiples.

[00:22:52]This means that your gut feeling might say that there if you have any pair whose LCM is not equal to this L, then their LCM has to be equal to a divisor of this L.

[00:23:11]Right? Because we said that all common multiples are actually divisible by LCM.

[00:23:18]Right? So, this number that you are just dealing with, this number that you are just dealing with.

[00:23:27]Yeah, this number that you are just dealing with, this must also have been the L It must have been something like this.

[00:23:36]Uh you must have computed the LCM of X and Y.

[00:23:42]And you multiplied it by two or multiplied it by three or multiplied it by four and that is how uh we got this reasoning, right? That even though LCM of four and six is not equal to 24, but this could have been equal to 12, 24, 36 because all of these, they are actually the multiples of the LCM. So, they are the multiples of the LCM. So, if they are the multiples of their LCM, then their actual LCM must be hiding as a divisor inside this L.

[00:24:17]So, this is what our gut feeling says, that if X and Y are divisors, then either their LCM has to be equal to L.

[00:24:29]Which we have already proved.

[00:24:31]Or if the Or if their LCM is not equal to L, then their LCM has to be equal to a divisor of this L.

[00:24:41]Now, this is what our gut feeling says, but we actually have to prove this fact and this fact is not at all obvious. In fact, I would say that this is the most [snorts] difficult fact to prove, but it kind of looks very intuitive.

[00:24:57]So, this time we want to find out how wrong is it to say that all the divisors pair will actually create an LCM L.

[00:25:04]So, this time we make a very bold claim that if you have a divisor pair and their LCM is not equal to L, then their LCM has to be a divisor of L.

[00:25:14]And to actually do a formal proof of this, you would need a different visualization of LCM. And for this I I have already created another video on my YouTube channel that talks about this different visualization of this LCM. And some of you might be aware of it.

[00:25:33]Some of you might be aware of it it and then some of you might not be aware of it, but this is also a very common and standard technique in competitive programming. So, one definition is that LCM is the lowest common multiple.

[00:25:47]Right? You write down all the multiples and then you find out the common ones and then you pick the lowest. But there is another visualization of LCM that I don't think a lot of people know that if you want to compute the LCM of X and Y, you compute it like so. You write down the prime factorization of X, suppose it is equal to P1 to the power X1 and uh P2 to the power X2 P3 to the power X3 and P4 to the power X4.

[00:26:27]And you write down the prime factorization for Y.

[00:26:32]Suppose it is equal to P5 to the power X5 and P2 to the power Or let me uh write it like so.

[00:26:53]Y is equal to P5 to the power X5 and P2 to the power Let me use Y2 over here.

[00:27:08]and P3 to the power Y3 over here.

[00:27:12]and P6 to the power Y6 and in fact also here also let me use Y5.

[00:27:25]Y5 So, you can see that X and Y have P2 as a common prime factor, P3 as a common prime factor, and P1 is unique, P4 is unique, P5 is unique, and P6 is unique. So, their LCM LCM of X and Y is actually equal to for each prime factor for each PI you compute maximum of XI and YI.

[00:27:59]So, since P1 is not present over here, so you retain this full P1. So, P1 to the power X1. And since P2 is common, so you retain P2 to the power max of X2 and Y2.

[00:28:17]Same for P3. So, you retain P3 to the power max of X3 and Y3.

[00:28:27]and you retain P4 as it is, you retain P5 as it is, you retain P6 as it is.

[00:28:33]Why?

[00:28:34]Because you still apply that max formula, but the exponent of P6 over here is zero.

[00:28:42]So, this is the alternate definition of LCM. In fact, GCD also has this alternate definition where where you use not max but min.

[00:28:53]Now, using this alternate definition of LCM, can you prove this fact that all the imposter pairs they will have if they do not have the LCM equal to L, they will actually have the LCM equal to one of the divisors of L.

[00:29:10]Now, you can see that it's very easy to prove this. Why? Because consider the prime factorization of L. It will be equal to P1 to the power X1, P2 to the power X2, P3 to the power X3 and P4 to the power X4.

[00:29:27]Then, consider X. X can only X cannot introduce new prime factors, so it can only take from P1, P2, P3, and P4. So, suppose X is equal to P1 to the power Y1 and P3 to the power Y3.

[00:29:45]And Y is equal to, let's say, P2 to the power uh Z2 and P1 to the power Z1, let's say.

[00:29:59]Then, LCM of X and Y, now you can notice that it would be P1 to the power max of Y1 {comma} Z1 and P2 to the power max of Z2 {comma} 0 and P3 to the power max of Y3 {comma} 0.

[00:30:19]But, now notice that max of Y1 {comma} Z1, but since Y1 since X is the divisor, Y1 has to be less than X1 and Z1 also has to be less less than uh Z1 also has to be less than X1. This means that whatever prime factor that you end up accumulating in the LCM, they will always look like P1 to the power M1 where M1 is less than equal to X1 and P2 to the power M2 where M2 is less than or equal to X2 and this number this number you can obviously see that this is this number is also a divisor of L. Why? Because any divisor can be constructed by having X1 plus one choices for the first exponent X2 plus one choices for the second exponent and so on.

[00:31:11]So now we have proven that even though this fact looked very obvious, we even our gut feeling told us us so that all the imposter pairs of the divisors if they if their LCM is not equal to L, then it has to be equal to a divisor of L.

[00:31:30]Now at some Now Now one thing you can notice that this actually just proves one thing that if you have a divisor pair X {comma} Y, then if their LCM is not L, then it has to be a divisor of L.

[00:31:49]But it doesn't actually say that all the divisors all the pairs XY So suppose Suppose L has a divisor equal to eight.

[00:32:04]Then this fact that we have just proven this this doesn't state that all the elements whose LCM is all the pairs whose LCM is equal to eight, which is this divisor, they are hiding inside this imposter pair list. This doesn't prove it. So the next fact, which is also not obvious, the next fact claims that all the imposter pairs they are actually exhaustive. And by exhaustive I mean that if you have your LCM is equal to L then you find out all the divisor pairs X Y and you also find out all the divisors. So suppose one divisor is two, second divisor second divisor is three.

[00:32:56]Then you have four as a divisor, then you have a 12 as a divisor, six as a divisor and so on. So we are claiming that all the pairs that achieve LCM six, they will indeed appear as an impostor pair over here.

[00:33:14]Previously we talked the other way around. We we said that if if the pair is an impostor then it has to be its its LCM has to be in this list. But but this time we are saying that every time an LCM is in this list, they also have to be in the impostor pair. And this is also actually not very obvious.

[00:33:35]But if you know this fact that divisors of a divisor are also a divisor of the original number. In fact, we already used this fact uh uh kind of in that previous prime exponent thing. But let's talk about it again. Like divisors of a divisor are also a divisor of the original number.

[00:33:56]So what this means that consider any number 48, right? So you see that 40 12 is a divisor of 48.

[00:34:12]Right?

[00:34:14]This means that anything that divides 12 should also divide 48. Hence the claim that divisors of a divisor are also a divisor of the original number. So any divisor at this level, they are also a divisor of this level.

[00:34:31]Now using this fact, you can now show that it is indeed exhaustive. Why is it exhaustive? Because the first fact claimed that if their LCM is indeed equal to L, then they have to necessarily appear as a divisor pair.

[00:34:50]This means that any number whose LCM is equal to 12, they have to appear as a divisor pair inside 12. But, if they are appearing as a divisor pair inside 12, then they also have to appear as a divisor pair inside 48. Why? Because the list of divisors of 12 is a subset of the list of divisors of 48.

[00:35:15]And that's why now you can see that this incorrect claim that we had earlier, that our brain thought that the LCM of 4 and 6 was equal to 24, it wasn't that wrong in the sense that yes, it is 24, but if you want to find out how many pairs, how many pairs achieve LCM is equal to 24, you will know that it hides a lot of information inside it.

[00:35:51]It hides the information how many pairs achieve the LCM 24, but it also hides the information how many pairs achieve the LCM 12. It also hides how many pair achieve the uh LCM eight.

[00:36:07]And four. And two.

[00:36:09]And one. And six. And so on.

[00:36:15]So, now you can see that you can now apply a dynamic programming kind of approach because this time, so in typical DP problems, you provide contribution to some other values.

[00:36:32]But now, this time your job is to deconstruct something. You have to reverse engineer something because this this DP value of L, suppose you define DP value of L is equal to D into D. Basically, all the divisor pair. Then, this time you have already computed this DP value, but this time this DP value is right now it is incorrect.

[00:36:58]So, then you have to uh remove all the imposter pairs. How can you do that? By subtracting the DP values of this, this, this, and this, and so on. So, let's move on to formalizing this dynamic programming.

[00:37:15]So, we define DP of L as the number of pairs that achieve LCM exactly equal to L. Notice the word exactly. This time we are not saying that LCM should be a divisor of L and whatnot. We just want to have a very simple DP definition which says that DP of L is this.

[00:37:39]But how do you compute the DP transitions?

[00:37:43]So, first, you can say that let's write a wrong DP and add corrections to it.

[00:37:52]So, you say that you compute the number of divisors. If this number is X, you compute the number of divisors, suppose you get D divisors, then you know that you can create D into D pairs, and they will achieve LCM equal to X, but we said that it is wrong, but not very wrong, right?

[00:38:13]So, first you start with that wrong DP, and you populate all of these values.

[00:38:19]But now, notice that if this is L and you have to correct the DP value of L then this time you have to subtract the DP value of let's consider this simple scenario 12.

[00:38:34]And what are the factors of 12? It is 1 2 3 4 6. Okay, these are the proper divisors of 12.

[00:38:46]So you have to [snorts] notice that all the pairs whose LCM is equal to one, they are hiding inside this.

[00:38:55]All the divisor pairs. All the divisor pairs whose LCM is equal to two, they are hiding inside this. All the pairs whose LCM is equal to three, they are hiding here. All the pairs whose LCM is equal to four, they are hiding here. All the pairs whose LCM is equal to six, they are also hiding here. In fact, all the pairs whose LCM is equal to two, they are 12, they are hiding over here.

[00:39:16]This means that if you can remove all the pairs that LCM is equal to a proper divisor, then what remains at the end will be equal to the number of pairs whose LCM is exactly equal to 12, but there is a caveat. The caveat is that you cannot subtract the existing DP values because the existing DP values are marked wrongly for one and two as well, right? For everything it is marked as D squared, D squared, D squared, D squared, and so on. So you have to subtract the correct DP value for all of these children.

[00:39:58]This means that if you can somehow find out the DP value of these, correct DP value of these, then you can subtract these correct DP values from this incorrect DP value of L and you would get your answer. Then you can already see why dynamic programming is being applicable over here because to find out the answer for L, you have to first find out the correct answer for all the numbers that are smaller than L.

[00:40:26]And if you are able to correct their DP values, then you can go over all of those DP values and then you can subtract the actual contribution that is hiding over here. And what will remain at the end is the actual pairs whose LCM is indeed equal to X.

[00:40:46]This means that if you can do the DP processing from left to right, then by the time you have arrived at L, you have already corrected the DP value of all of the smaller nodes. So, then it is actually allowed to just do DP of L minus equal to DP of imposter where imposter is a divisor of L.

[00:41:11]Why is this not wrong? Because you started with D square for every imposter, but then since you are processing everything from left to right, you are correcting all the DP values from left to right.

[00:41:27]And why will this be correct? Because of this fact that all the divisors of any number, they are strictly less than or equal to L. So, that's why you will never subtract a bad contribution. Right? Whatever contribution that you subtract, that will actually be equal to the exact number of pairs whose LCM is equal to one, whose LCM is equal to two, whose LCM is equal to three.

[00:41:54]So, all we have to do is just simulate this process and you can see that we only need the divisor list to do this DP operation.

[00:42:05]So, let us look at the code for this.

[00:42:07]So, first we write a simple utility function that computes the divisor of any number. and this is also a standard technique in competitive programming, but again, I believe not everyone is aware. And this is standard trick says that every divisor appear in conjugate. So, if you have a divisor X, then N by X is an integer, but not just an integer, it is also another divisor. This means that if you look at this expression X less than N by X, then you can see that X square is less than equal to N. It means that X less than equal to root N.

[00:42:48]This means that for every conjugate pair, what the smaller element of the conjugate pair is on the left hand side of root N and the larger element is on the right hand side of root N. So, you only have to iterate over root N and add the conjugate pair manually. And this time, you have your O of root N algorithm to compute the list of all the divisors. And once you have this formula, you start doing your DP. So, first of all, you write the wrong DP for everything. And in the wrong DP, you add everything including your imposters. So, the your your imposters would be you compute the number of divisors and D into D is the number of pairs that has LCM equal to L, but there are imposters and the imposters are the divisors.

[00:43:38]So, then you try to fix the DP value and you try you can fix the DP value by subtracting the actual DP contribution from left to right. So, you go from left to right and for each number, you first find out all of its divisors. And by now, you can assume that all this DP of divisor, this will be the corrected value because divisor is always less than the number. So, you subtract the correct contribution of the divisor and what would remain after this loop is the correct value of dp of i. And by definition, dp of i meant the number of pairs with LCM equal to l. So, this time complexity is O of root n, and this time complexity is just n root n.

[00:44:23]And this is also n root n. So, you see that that complicated problem we were able to just solve in O of n root n.

[00:44:34]Now, we know one algorithm that can solve how many pairs achieve LCM is equal to l. Now, if you have watched the video so far, that's already good enough. But in the remaining part of this video, I will show you another trick that is also a very standard technique in dynamic in competitive programming that can achieve the same thing in n log n, and it won't require O of n root n.

[00:45:01]So, now this might be a bit interesting to some of you but how can you actually subtract the contribution of all the divisors without actually iterating over them, and how can you actually get rid of this root n factor and replace it with this log n? So, this is also something that is not obvious. So, let's talk about it.

[00:45:22]So, how do we uh improve the time complexity?

[00:45:27]So, all of this So, again, our idea is same. We want to start with the incorrect dp, and the incorrect dp says that claim that all the divisor pairs are LCM equal to x.

[00:45:43]So, claim that all the divisor pairs x and y, which will be d squared divisor pair, uh they have LCM equal to l, but realize later that some imposters are there, and the imposters are one are the ones whose uh imposters are the one that are divisors of this l.

[00:46:02]So you have to uh subtract their contribution so that core idea is the same but we want to do it in a smart way.

[00:46:10]So So this time what we'll do is we focus on this aspect. Remember that earlier we talked about this fact that divisors and multiples are siblings, right? This fact. This fact will come in very handy now.

[00:46:29]How are the siblings? Because we said that if X is a multiple of Y then you can claim that Y If X is a multiple of Y then Y divides X. So that's why they always occur in pairs. So whatever you can do with divisors you can also deal also do with multiples. And remember this fact, this is actually more powerful than you think. That whatever you can do with the divisors you can do the same thing with multiples.

[00:47:06]And here we were doing some shenanigans with the divisors. So what if we flip the perspective? So in fact this technique is by itself very useful in in competitive programming that you have to flip the perspective. Think not from the perspective of divisors but think from the perspective of multiples.

[00:47:32]So in fact this technique you might you must have seen in a lot of contribution technique problems as well.

[00:47:39]And what we will do is instead of trying to fix an L and then trying to remove all the imposters, we we will pick one imposter and we'll see in how many L it could be be So let's suppose this number is two.

[00:48:00]So, if I give you the correct value of DP of two, because of course you need the correct value to remove the contribution, then can you figure out in which L is two hiding as an impostor? It will be all those L where two appears as a divisor.

[00:48:21]But, you can flip this narrative and you can say that these L's are nothing but the multiples of two, which is nothing but this element, this element, this element, this element, this element, and so on.

[00:48:35]So, if you already have the If you already have the contribution If you already have the correct value of DP of two, why not just go ahead and we know that this right now this value is wrong, because it is set to D squared, but why not just go to this value and subtract DP2 eagerly? So, this eagerly subtraction that we are doing, this will not make this value correct immediately, because there could be other impostors hiding over here.

[00:49:07]But, you do do the subtraction for all of these multiples, and then let's say you reach three, and let's say somehow I give you the correct DP value of three. Then, you can apply the same trick for three. So, for three, you find all its multiples, so this would be six, and then you go to nine, and then you go to 12, and so on, and you subtract DP of three from all of them.

[00:49:34]So, we are not claiming that DP of six will be corrected so far.

[00:49:39]It won't be.

[00:49:40]But, at least you have you are not If you are three, then you are not an impostor over here.

[00:49:50]Right? Any Any divisor pair that achieves LCM three, they are not an impostor over here.

[00:49:58]Now notice that all of this hinges on the fact that you know the correct value of DP two and you know the correct value of DP three when you do this when you subtract their contribution.

[00:50:11]But how can how are you sure that you know the correct value of DP of two?

[00:50:15]Here you can use induction and you can see that if you are processing from left to right and for each impostor X that you see first, so if you remove if you consider the first element and if you go ahead and remove the contribution of one from every multiple of one, then one will not act as impostor in any of them.

[00:50:41]Now what will happen when you encounter two?

[00:50:44]This time you can actually claim that DP of two will already be corrected already points to the correct value by the time you reach here. Why? Because the only multiples of two would have been on the left-hand side and you have already processed on the left-hand side with the correct value of one which we know.

[00:51:02]So DP of two is correct. It means that you now subtract the contribution of DP of two from here, here, here, here and so on. Now when you reach DP of three, this time DP of three also will be correct. Why? Because you all the multiples of three are to the left-hand side and you already know the correct value of left-hand side and you have subtracted their contribution. There So those impostors are gone. Then when you reach DP of four, all the DP value of four will be correct. So in fact this idea is the one that empowers that sieve algorithm.

[00:51:37]Now now you might wonder that okay, we can do this complicated thingy where we don't deal with divisors, we deal with multiples, but then how does it actually help us? How does it improve the time complexity? Because if divisors and and multiples are indeed siblings, then doing going from X to Y versus going from Y to X should be the same thing.

[00:51:57]But surprisingly, this is also another well-known technique in competitive programming that this doing doing the multiple route doing by the multiple way is actually faster and the time complexity is N log N. Why is it N log N because you'll process the first element one and for one there will be N elements that you will have to go through.

[00:52:24]But for two, when you are processing two, you will only process N by two elements because if you start making a jump of two, after N by two elements, you will exceed N.

[00:52:37]And when you are processing three, you will only touch N by three element because if you start making bigger jumps, then in just N by three steps, you will exceed N and you don't want to go beyond that. So, this will continue like so plus N by four plus N by five plus N by six and so on and you will recognize that this is nothing but your this is bounded by the sum of harmonic series which is N log N. And that's why doing in this fancy alternative way brings down the time complexity from N root N to N log N.

[00:53:15]Not that it is absolutely required. In fact, I was able to get an AC with both of these approach for this problem. But anyway, this N log N approach is very good to know because this is what will actually be reused in a lot of DP problems that deals with GCD, Mobius function, and LCM, and so on.

[00:53:38]So, this time you can see that we are using the DP transition and our trick is same, but this time we are not using a push DP. We are instead doing a pull DP. And what is the difference between them? In push DP, you try to fix an L and you try to find out what should be correct value of DP of L be.

[00:53:59]So, in order to correct DP of L, you start with a wrong value D squared and then you subtract all the imposters. So, that is why you are Uh that is why you are pulling from your divisors. You are pulling the contributions from your divisors. And this time you want to do a push DP. And in push DP, you start with a multiple and you start pushing your contribution.

[00:54:24]And And in this context, pushing your contribution actually means taking back your contribution from these D squared pairs for each of your multiples. So, finally, let's look at this code. And it is actually counterintuitive that the code for this complicated part is much more simpler and easier to understand than the original N root N complexity code because here you see that you had a utility function and then that does this. But this time, with this push DP trick, it's just this much code and you will see that it is actually very easy to understand what we are doing. So, first, you have to count the number of divisors of each integer. And previously, we counted that in root N by actually computing the divisors. And this time you can already see that trick that within N log N you can actually find out the number of divisors by doing a push DP instead of a pull DP. So, you fix any divisor D and you iterate over all of its multiples and you increment their divisor count. So, this is Again, this is You can also say that this is a contribution technique because you are contributing. So, each divisor is contributing to all of its multiples.

[00:55:45]So, in this manner you have your divisor count and if you have your divisor count, you can uh initialize your DP incorrectly with D into D pair.

[00:55:55]Right? That is what you needed. And to fix your DP, all you have to do is follow the same trick again of push DP that you iterate through all the divisors.

[00:56:05]And then you remove your contribution from your multiple. So, that's why you do 2 into D and you see that this trick that we are using that it starts with D and plus equals to D. This plus equals to D and not plus equal to I is what ensures that the time complexity is n log n because this plus equal to D means that you're doing a hop of D steps every time.

[00:56:31]One minor thing that you would notice that in this first version, when we're counting the divisors, we started with D.

[00:56:38]But in the second version, when we're uh dropping the contribution, we started with 2 into D. And this is obvious because if you are D, then if you're a number n, then n is also a divisor of n.

[00:56:56]Right? And that's why we said that n is also a multiple of n.

[00:57:01]So, that's why we started with this. But when you want to pull the contribution, you don't actually want to subtract the DP value of n, right? Because you only want to subtract the proper divisor. And by proper divisor, I mean the divisor which is not exactly equal to n. So, that's that's why we start this loop as 2 as 2 into D, but this loop as D.

[00:57:23]And once you are done with this DP transition, then you can notice that the final DP value would actually represent for each DPL, it will actually represent how many pairs achieve LCM L.

[00:57:39]And this code that you see on the screen, this is a recurring theme in a lot of number theory problems that deal with GCD, LCM, divisors, and multiples.

[00:57:50]So, make sure that you understand this idea thoroughly so that you can actually reuse it. Actually, this n root n thing might not be reusable that much, but it's still that was a good starting point for us to understand what the DP is trying to do, and then we optimized it via this harmonic series trick.

[00:58:10]So, then you can see that n log n is actually much easier to code and understand and maintain.

[00:58:17]So, which is an interesting idea that the harder the harder version is actually easier to code and understand.

[00:58:26]And yeah, that was it about the video.

[00:58:29]Do let me know what you Do let me know in the comment section what do you think about the approaches that we have discussed, and if you have any other alternate approach to solve this problem because I know there is an alternate way to solve this problem that doesn't involve DP. I think I also saw that in the official editorial. So, do let me know how did you solve it in the in the official contest. And of course, if you are interested, there is also also a version with 10 to the power 9 where you have to find how many pairs achieve LCM greater than 10 to the power 9, and where there you again have to use your intuition that LCM is mostly x into y except some cases where it's not, and those cases are actually, technically speaking, they are where x It is only possible when x and y are coprime. So, there what you do is you you try to So, if your brain thinks that LCM of x and Y is equal to X into Y, let it think so and you can do that by you can correct your brain by saying that okay, if X and Y if they have the GCD G, then let's write G as G into A and Y as G into B and now your brain can keep on thinking that LCM is equal to A into B and this G is actually a common factor with the caveat that GCD of A comma B is equal to one. So it starts from this fact and yeah, it's a bit complicated so that's why I did not add that in this video, but hope that you at least got to learn something new from this video. That's all for today. Thank you.