CODECHEF COOK38 RRMATRIX

Problem Statement

Let 'A' be a R x C  Matrix. Elements in 'A' are filled from 1 to R*C in row-major order. 'B' is also a R x C Matrix where the elements are filled in column-major order.


Find number of cells which satisfy the property A_i,j ==  B_i,j.

For a brief problem statement click here.

Solution

Consider an element ( i, j ). In Matrix A, the element is located at

Pos_old = i * C + j.

In Matrix B (Transposed Matrix of A), the same element will be located at

Pos_new = j * R + i

To satisfy the property A_i,j ==  B_i,j. Pos_old and Pos_new should be equal.

i * C + j == j * R + i

The equation can be simplified as i * (C-1) - j*(R-1) == 0

i = ( (R-1) / (C-1) ) * j

Clearly 'i' should be an integer. The eq. is of the form i = ( a / b ) * j. For 'i' to be integer, 'j' should be a multiple of 'b'.

a = ( R - 1 ) / GCD( R-1,C-1)    -----------------------------------------------------------------> 1

b = ( C-1 ) / GCD( R-1,C-1 ).     -----------------------------------------------------------------> 2

'j' is the column index. Its values ranges from 0 to C-1. So, the maximum value 'j' can take is C-1. Therefore , the no. of  unique possible values of 'j' are j / b . In other words, number of multiples of 'b' in the range 0 to C - 1.

From 2,  j / b = ( ( C - 1 ) * GCD ( R-1, C-1 ) ) / ( C - 1 ) which is simply GCD ( R-1, C-1 ).

Therefore, No. of Elements which satisfy the property is GCD(R-1,C-1) + 1.

Note:    +1 is the first element in the Matrix.

Boundary Conditions

• M == 1,  No. of Elements which satisfy the property is N


• N == 1,   No. of Elements which satisfy the property is M.

Code:

[sourcecode language="cpp"]
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
if(b == 0)
return a;
return gcd(b,a%b);
}
int main()
{
std::ios_base::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
int m,n,g;
cin>>m>>n;
if( m < n )
std::swap(m,n);
g = gcd(m-1,n-1);
if( m == 1 || n == 1 )
cout<<std::max(m,n)<<endl;
else
cout<<g+1<<endl;
}
}
[/sourcecode]