KingXNewCurrency | Topcoder Archive

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 given ints 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.

Definition

Class:: KingXNewCurrency
Method:: howMany
Parameters:: int, int, int
Returns:: int
Method signature:: int howMany(int A, int B, int X)
(be sure your method is public)

Constraints

A, B, and X will each be between 1 and 200, inclusive.
A and B will be different.

Examples

```
5
```
```
8
```
```
5
```
```
Returns: 5
```
These are the 5 possible currency systems: {5, 1}, {5, 2}, {5, 3}, {5, 4}, and {5, 8}.
```
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.
```
7
```
```
4
```
```
13
```
```
Returns: 1
```
The only possible currency system is {13, 1}.
```
47
```
```
74
```
```
44
```
```
Returns: 2
```
The two possible currency systems are {44, 1} and {44, 3}.
```
128
```
```
96
```
```
3
```
```
Returns: 65
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.