# RRMATRIX - Editorial

Practice

Contest

Author: Roman Rubanenko
Tester/Editorialist: Utkarsh Lath

Simple

# Pre-requisites:

High school maths

# Problem:

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:

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.

## Boundary cases

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

# Solutions:

9 Likes

if n=1 and m=1 then answer will be 1,
but this totorial say(boundary case) that ans =2 how ?

3 Likes

for n=1 or m=1 shouldnt the answer be just max(n,m) ?

1 Like

for n=1,m=1 obviously answer is 1 only.
You can do it like: if(n==1 && m==1) ans=1 else ans=gcd(n-1,m-1)+1

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.

I hope you’ll not mind that I’ve edited the post, but there was an obvious mistake in the boundary case.

1 Like

you do not need to check if(n==1 && m==1) because you have gcd(0,0) will return 0

Why does this C# code produce a wrong answer?

``````enter code here
static void Main(string[] args)
{
int cnt2;

for (int t = 0; t < T; t++)
{
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);
}``````
1 Like

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!!

Strangely (to me), the GCD needed to have variables a and b defined as long (instead of int) to work:

``````    static long GCD(long a, long b)
{
if (b == 0) return a;
return GCD(b, a % b);
}
``````

Thus, I defined cnt2 as a long also.
It does not seem to me that a, b, a%b, or GCD(a,b) would ever be greater than an int value.

2 Likes

Strangely (to me), the GCD needed to have variables a and b defined as long (instead of int) to work:

``````static long GCD(long a, long b)
{
if (b == 0) return a;
return GCD(b, a % b);
}
``````

Thus, I defined cnt2 as a long also. It does not seem to me that a, b, a%b, or GCD(a,b) would ever be greater than an int value.

when “if (n == 1 || m == 1)” comes out true then output should be 1.

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).

thanks @alex_2oo8

may be the problem was elsewhere, because everyones solution used 32 bit numbers only

1 Like

going by strict definition of divisors, gcd(0, i)should be undefined. However, people conveniently extend it to mean that gcd(i, 0) = i.

@utkarsh_lath [Not something relating to this problem] I remember a problem from some previous contest, where 0^0 was conveniently taken as 1. That didn’t go by strict definitions.

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.

1 Like

Just a note: in editorial are used 0-based indexes, while in problem statement there wer 1-based indexes used…

1 Like

0 based indexes makes reasoning much easier to convey / come up with.

1 Like