BlueBlisteringBarnacles's blog

Maybe a miswriting in Codeforces round 665 problem C
By BlueBlisteringBarnacles, history, 4 years ago, In English

Hello guys. in codeforces round 665 problem C , it was written that: {In one operation, you can choose two different indices i and j (1≤i,j≤n). If gcd(ai,aj) is equal to the minimum element of the whole array a, you can swap ai and aj. gcd(x,y) denotes the greatest common divisor (GCD) of integers x and y.} so , from this i understood that the gcd should equal to the mn right? so i wrote this program: 90592067 but it got me WA. then i changed it to if gcd % mn == 0 in here 90635208 and it got me accepted. did i misunderstand the problem or it was written wrong? and thx.

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The question is correct. GCD should be Minimum of the array. The reason why your second approach gets AC and not the first one is that you are not taking GCD of the array element not in right place with Minimum itself.

Suppose minimum is 2 and you are taking GCD of 8 and 4. GCD(8,4) = 4. But you can still swap 8 and 4 by using 2 with both (kinda 3 way swapping). Hence when you do GCD%min, if the GCD itself is divisible by min, you get AC.

Hope I am making sense.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    oh ok thx man. i was thinking in this example particularly , but i didnt think of it in a 3 way swap. thx for explaining it to me.

    → Reply