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 ?
For 0 ≤ i < N, 0 ≤ j < M, the (i,j)th entries are:
Ai, j = i * M + j + 1
Bi, 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.
N = 1 or M = 1, in which case the answer is max(N, M).
enter code here
static void Main(string args)
int T = int.Parse(Console.ReadLine());
for (int t = 0; t < T; t++)
string s = Console.ReadLine().Split();
int n = int.Parse(s);
int m = int.Parse(s);
if (n == 1 || m == 1)
cnt2 = Math.Max(n, m);
cnt2 = GCD(n-1, m-1) + 1;
static int GCD(int a, int b)
if (b == 0) return a;
return GCD(b, a % b);
Its all about conventions and widely accepted norms. Whether 0^0 is 0 or 1 is usually clear from the context.
Sometimes people give special mention to such things, sometimes assume that others are aware of it.