Fun With Numbers
All submissions for this problem are available.
Munchi and BlackHammer like to play games. BlackHammer gives Munchi 2 numbers N and M and allowes him to perform following operations on the numbers-
- Subtract 1 from any one of the numbers.
- Divide both the numbers by their gcd.
Now, Munchi wants to know the minimum number of operations to convert (N,M) to (1,1).
- First line contains T - Number of test cases.
- Next T lines contain 2 integers N, M
OutputMinimum operations to convert both N and M to 1.
-Operation 2: N=2 M=1
-Operation 1(on N): N=1 M=1
|Tags||dynamic-programming, easy, nkcb2016, shivam_wadhwa|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.