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

CandidFlakes's blog

Why the common multiples have to be least?
By CandidFlakes, history, 15 months ago, In English

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!

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Try to solve the problem with $$$\min$$$ instead of $$$\gcd$$$.

Solution

Prove that, if there is any valid $$$b$$$, the one in the spoiler is also valid.

Why is this problem similar to your problem?

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hint: use this "definition" of GCD, and solve for each prime independently.

      → Reply