KingXNewCurrency
SRM 537 · 2011-11-22 · by fushar
SRM 537 · 2011-11-22 · by fushar · Brute Force, Simple Math
Problem Statement
Problem Statement
King Dengklek is the perfect king of Kingdom of Ducks, where slimes and ducks live together in peace and harmony.
Kingdom of Ducks has a pretty strange currency system. There are only two coin types: one with value A and one with value B, where A and B are different. This currency system is denoted by {A, B}. These two coin types are sufficient for daily transactions, because all prices in this kingdom are in the form of (A*p + B*q) for some non-negative integers p and q. Therefore, slimes and ducks can pay for any goods with a combination of the two coin types.
Bored with the current system, King Dengklek considered another currency system with two coin types: one with value X and one with value Y, where X and Y are different. Of course, with this new system, combinations of the two new coin types must make it possible to pay all the prices one could pay with currency system {A, B}. (Note that the new coin types may also make it possible to pay some additional prices.)
You are givenint s A, B, and X. Return the number of different positive integers Y (other than X) such that the currency system {X, Y} can be used to replace the currency system {A, B}. If there is an infinite number of possible values for Y, return -1 instead.
Kingdom of Ducks has a pretty strange currency system. There are only two coin types: one with value A and one with value B, where A and B are different. This currency system is denoted by {A, B}. These two coin types are sufficient for daily transactions, because all prices in this kingdom are in the form of (A*p + B*q) for some non-negative integers p and q. Therefore, slimes and ducks can pay for any goods with a combination of the two coin types.
Bored with the current system, King Dengklek considered another currency system with two coin types: one with value X and one with value Y, where X and Y are different. Of course, with this new system, combinations of the two new coin types must make it possible to pay all the prices one could pay with currency system {A, B}. (Note that the new coin types may also make it possible to pay some additional prices.)
You are given
Constraints
- A, B, and X will each be between 1 and 200, inclusive.
- A and B will be different.
Examples
0)
5 8 5 Returns: 5
These are the 5 possible currency systems: {5, 1}, {5, 2}, {5, 3}, {5, 4}, and {5, 8}.
1)
8 4 2 Returns: -1
All prices are multiples of four. Since a coin type with value 2 alone can pay any price that is a multiple of four, there is an infinite number of possible values of Y.
2)
7 4 13 Returns: 1
The only possible currency system is {13, 1}.
3)
47 74 44 Returns: 2
The two possible currency systems are {44, 1} and {44, 3}.
4)
128 96 3 Returns: 65
Submissions are judged against all 142 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class KingXNewCurrency with a public method int howMany(int A, int B, int X) · 142 test cases · 2 s / 256 MB per case