Not able to solve

#1

Hello.
I am doing this question from codeforces…
https://codeforces.com/problemset/problem/1266/C
I am not able to arrive at proper logic…
Even editorial is a little bit not intuitive for me.
Please tell me …what should be our approach to this question.
Thanks

#2

hello @ashishnnnnn

it is observation based problem.
some points that i want to clear.
a) we want r+c distinct values to make the matrix diverse
b) becuase we want r+c distinct values that means gcd of each row (r rows are there) and gcd of each column(c columns are there) must be distinct right?

c) we want to minimise the maximum among all those gcd right?
now one thing is very much clear is that we cannot make our answer less than r+c .
how?
we want r+c positive ditinct value whose all elements are distinct
the best r+c values we can think of is { 1, 2,…3…r+c} (all numbers from 1 … r+c) .
why this combination ?
it is becuase we have r+c as maximum and if we change this combination than maxximum will be more than r+c so its better to stick with this combination.

now its easy. u just have to make gcd of rows and coulmn equAL to {1,2,r+c}

this is what they are doing. now read editorial once again it will make sense now.

one line summary-> answer cant be less than r+c becuase {1…r+c} is the only combination that gives leas maximum value

#3

Thank you… Very… Very Much…
You have explained it… so well that… i was able to solve it without seeing editorial.
Thank you once again :slight_smile: