Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

Why the common multiples have to be least?

Revision en1, by CandidFlakes, 2023-08-22 18:10:11

I was trying to solve this problem.

I went through it's tutorial and understood the following approach, Because the greatest common factor of b[i] and b[i+1] is a[i], and the greatest common factor of b[i+1] and b[i+2] is a[i+1], so b[i+1] is not only a multiple of a[i], but also a multiple of a[i+1], so when we construct the b array as b[i] = common multiple of a[i] and a[i+1].

But, in the tutorial they have taken Least common multiple. Please point me out the reason for taking the least common multiple because I am able to come up with some examples in which even if I don't take LCM(just take general common multiples) then also I get correct result.For example, consider a = {4,2}, then b could be {4,8,2}, here you can see b[2]=8 and b[2]!=lcm(a[1],a[2])=4.

What are the reasons which make it necessary to take LCM?
I will be thankful for any help!

Tags lcm, gcd, __gcd, multiple

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English CandidFlakes 2023-08-22 18:10:11 969 Initial revision (published)