Codeforces round 201 div2 C

This question editorial is not that good. Someone asked a question about it but nobody responded. So I thought I may get an answer here. My question as always is

  • How do they arrive at the idea? What are the thought processes that lead to the solution. Please give some intuitive idea.
    Thanks in advance.

The EDITORIAL:Problem -A

1 Like

Hi a____,

lets take example of two numbers 6 and 15

so we will get different numbers while subtracting each other - 15-6=9 , 9-6=3 , 15-3=12 so we got 3,6,9,12,15 after solving so why we are not getting less than 3 ?

so reason is GCD because if you subtract any two number and get new number then again subtract form each other to get different number each time then smallest number can not be less than GCD of initial two.

eg. 6 = 3$2 and 15 = 3$5 here GCD is 3 hence when you will subtract these two then :-

15-6 = 3$5-3$2 = 3*(5-2) = 3*(3) = 9

9-6 = 3$3-3$2 = 3*(3-2) = 3*(1) = 3

15-3 = 3$5-3$1 = 3*(5-1) = 3*(4) = 12

so while subtracting GCD factor will always remain common to both hence you cant obtain less then this and our objecting is to get smallest number so that we can generate maximum amount of distinct number.
it was for two number like this you can do for more than two number procedure will be same

lets take GCD is 1 (one) then we can generate all numbers form 1 to max.
i hope you got that

if(any doubt) ask ;

else code;

2 Likes

@admin123.: Yes! I have understood the explanation. Thanks…Actually I can’t get this idea during contest…Later reading the editorial I couldn’t get the intuitive approach. Any suggestion where I can get tons of these concepts?

that place is this !

you will get all of those concept like this one hence practice and discuss there is no alternative :slight_smile:

happy coding…

1 Like