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!
Try to solve the problem with $$$\min$$$ instead of $$$\gcd$$$.
It's optimal to set $$$b_i = \max(a_i, a_{i+1})$$$.
Prove that, if there is any valid $$$b$$$, the one in the spoiler is also valid.
Why is this problem similar to your problem?
Thanks so much!
I am able to verify that if there is any valid b then the one in the spoiler is also valid. But, I still can't see the similarity between these two problems! Please give little more hint.
Hint: use this "definition" of GCD, and solve for each prime independently.