### PROBLEM LINK:

**Author:** Shivam Wadhwa

**Tester:** Shivam Manchanda

**Editorialist:** Shivam Machanda

### DIFFICULTY:

EASY

### PREREQUISITES:

DP , 2D-DP

### QUICK EXPLANATION:

For every pair of N and M there are atmost 3 ways to proceed. Decrease N, or decrease M or N/=GCD(M,N) and M/=GCD(M,N).

### EXPLANATION:

Make a 2-D array DP, where DP[i][j] represents minimum ways to make i and j both 1. You can now make a recursive definition:

```
DP[1][1]=0;
for(i from 1 to N)
{
for(j from 1 to M)
{
if(i==1 && j==1)
continue;
if(gcd(i,j) != 1)
minimum from (DP[i/gcd][j/gcd]+1 , DP[i-1][j]+1 , DP[i][j-1]+1 );
else
minimum from ( DP[i-1][j]+1 , DP[i][j-1]+1 );
}
}
```

### Time complexity

O(N*M)

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

Solution can be found here.