PROBLEM LINK:
Setter: Abdullah Aslam
Tester: Michael Nematollahi
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy.
PREREQUISITES:
Observations and Modular Multliplicative Inverse.
PROBLEM:
Given a grid with N rows numbered from 0 to N-1 and M columns numbered from 0 to M-1 and another integer K, you start from cell (0,0). Determine the minimum number of moves in which you can visit all cells if you can move in the following manner, or determine it is impossible to reach each cell at all.
From cell (r, c), you can move to either of the following three cells.
- (r, (c+K) \% M)
- ((r+K)\%N, c)
- ((r+K)\%N, (c+K)\%M)
EXPLANATION
For the first subtask, it is easy to see that if K = 1, we can always visit any cell by above operation, and if K = 2, we need both N and M to be odd, otherwise we cannot visit odd numbered rows/columns. If we can visit, the minimum number of operations is always N*M.
Coming to final subtask now.
Firstly, assume there’s a single row. Now, the problem becomes to reach all cells (0, y) starting from (0,0) where, in a single step, you can move from (0, c) to (0, (c+K)\%M) (or moving K steps to the right).
Lemma: If we can reach from (0, c) to (0, (c+1)\%M) just by operation of moving K steps to the right, we can reach all cells in the same row.
Proof: If By starting in column c, moving K steps to the right, say y times, we reach column (c+1)\%M, we can again apply operation y times to reach (c+2)\%M and so on. We can continue this until we have visited all cells.
Let us determine the number of steps to move from (0, c) to (0, (c+1)\%M).
Starting from column c and moving y*K steps to the right implies final position (c+y*K) \bmod M which should be (c+1) \bmod M for some y for reaching position (0, (c+1)\%M).
This implies (c+y*K)%M = (c+1)\%M which implies y*K = 1 \bmod M. Multiplying both sides by K^{-1}, we have y = K^{-1} \bmod M.
Now, the criteria for a valid y is that K^{-1}\bmod M exists which requires gcd(M, K) = 1. We can see this is also sufficient condition for existance of y.
Coming to the original problem, we can see that we can apply the operations for each dimension independently. For checking whether a valid tour exists, we can treat the original problem as following two sub-problems.
- Only one column and N rows for given K
- Only one row and M columns for a given K.
A valid tour exists in original problem if and only if valid tour exists in both sub-problems, which implies condition both gcd(N, K) and gcd(M, K) should be 1.
Now, coming to the minimum number of cells visited, it can always be seen that we never need to visit a cell twice, leading to exactly N*M cells in the tour.
Example
Consider following grid with N = 2, M = 5 and K = 3. Since gcd(2,5) = 1 and gcd(3, 5) = 1, valid tour exists.
0 1 2 3 4
5 6 7 8 9
One valid tour is 0->3->1->4->2->5->8->6->9->7
The idea for a valid path is to keep moving right, till the next cell is already visited, and in next move, move K steps down too, along with K steps to the right.
TIME COMPLEXITY
Time complexity is O(log(X)) per test case due to GCD operation where X = max(N, M, K).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define PB push_back
#define N 300101
#define SZ 3001
#define LB lower_bound
#define M 1000000007
#define UB upper_bound
#define MP make_pair
#define LD long double
#define F first
#define S second
int main()
{
LL k,i,j,lt,tc,d,r,q,y,z,v,x,m,n;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>lt;
while(lt--)
{
cin>>n>>m>>k;
assert(n>=1&&n<=1e9);
assert(m>=1&&m<=1e9);
assert(k>=1&&k<=1e9);
if(__gcd(m,k)==1&&__gcd(n,k)==1)
{
x++;
cout<<n*m<<endl;
}
else
{
y++;
cout<<-1<<endl;
}
}
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int te; cin >> te;
while (te--){
int n, m, k; cin >> n >> m >> k;
if (__gcd(n, k) > 1 || __gcd(m, k) > 1)
cout << "-1\n";
else
cout << 1ll*n*m << "\n";
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class GRIDTOUR{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
long n = nl(), m = nl(), k = nl();
if(gcd(m,k)==1 && gcd(n, k)==1)pn(n*m);
else pn(-1);
}
long gcd(long a, long b){
return b==0?a:gcd(b, a%b);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new GRIDTOUR().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, if you want to. (even if its same 
) . Suggestions are welcomed as always had been. 
