PROBLEM LINK:Author: Shivam Wadhwa DIFFICULTY:EASY PREREQUISITES:DP , 2DDP 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 2D array DP, where DP[i][j] represents minimum ways to make i and j both 1. You can now make a recursive definition:
Time complexity$O(N*M)$ AUTHOR'S AND TESTER'S SOLUTIONS:Solution can be found here. asked 02 Oct '16, 10:45
