Блог пользователя BlueBlisteringBarnacles

Автор BlueBlisteringBarnacles, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.