Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

Why the common multiples have to be least?

Правка en1, от 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!

Теги lcm, gcd, __gcd, multiple

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский CandidFlakes 2023-08-22 18:10:11 969 Initial revision (published)