favorite We need a little bit of your help to keep things running, click on this banner to learn more

Dynamic programming

Frobenius coin problem

There are coins of two denominations x and y respectively. Find the largest sum S that cannot be represented with these two denominations (assuming infinite supply of coins) and the total number T of such not representable amounts. If such value does not exist, print "NA".


Two positive integer x and y (1 < x, y109).


Print in one line two numbers: S and T.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2 5
Output example #1
3 2
Input example #2
5 10
Output example #2