Given two matrices A and B, both of them having N rows and M columns. The cells of A are numbered in row major order, and cells of B are numbered in column major order. How many cells appears at the same location in both the orderings ?

Explanation:

For 0 ≤ i < N, 0 ≤ j < M, the (i,j)^{th} entries are:

A_{i, j} = i * M + j + 1
B_{i, j} = j * N + i + 1

equating the two, we get

i * M + j + 1 = j * N + i + 1
⇒ i * (M-1) = j * (N-1)
⇒ i / j = (N-1) / (M-1) = p / q
⇒ i = l * p, j = l * q for 0 ≤ l ≤ min((N-1) / p, (M-1)/q)

where p/q is reduced form of (N-1)/(M-1).

However, if g = gcd(N-1, M-1),

(p, q) = ((N-1)/g, (M-1)/g)

Therefore, (N-1) / p = (M-1) / q = g
and the cells which get same numbering are (l * p, l * q) for 0 ≤ l ≤ g, which are g+1 in number.

Boundary cases

N = 1 or M = 1, in which case the answer is max(N, M).

actually there is no need of boundary conditions.
in case when (n==1||m==1) then gcd(0,n(or)m) will be 0 and the answer will itself become 1 and correct.

enter code here
static void Main(string[] args)
{
int T = int.Parse(Console.ReadLine());
int cnt2;
for (int t = 0; t < T; t++)
{
string[] s = Console.ReadLine().Split();
int n = int.Parse(s[0]);
int m = int.Parse(s[1]);
if (n == 1 || m == 1)
cnt2 = Math.Max(n, m);
else
cnt2 = GCD(n-1, m-1) + 1;
Console.WriteLine(cnt2);
}
}
static int GCD(int a, int b)
{
if (b == 0) return a;
return GCD(b, a % b);
}

long long gcd(long long a,long long b)
{while(a>0&&b>0)
if a>b a%=b;
else b%=a;
return a+b;
}
so if either m=1 or n=1 then g=gcd(m-1,n-1) becomes zero and g+1 will give 1 which is correct answer!!

What if I start calculating from 1- based index. e.g. A(i,j) = (i-1) * M + j and B(i, j) = (j-1) * N + i then by equating these two, I get i(M-1)-M= j(N-1)-N ; How to proceed further?

I am not able to understand the last part, that how come answer for no of matches become g + 1. I got the same equation given in editorial, but at the end how come this happens --> i = lp and j = lq and from this how do we draw conclusion that g + 1 is no of matches in both the matrices.
Please Help!

Manal, I think you mean “if (n==1 && m==1)” then output should be 1. Otherwise, if n==1 or m==1 then the answer would be the other number (e.g. n=1, m=5, then output 5).