Problem Statement
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
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
1
2
1
Returns: -1
200
199
200
Returns: 2
200
199
199
Returns: 12
1
200
1
Returns: -1
100
200
3
Returns: 51
128
162
2
Returns: -1
162
128
6
Returns: 49
97
47
61
Returns: 1
2
3
5
Returns: 1
37
70
33
Returns: 4
1
100
100
Returns: 1
200
150
5
Returns: -1
200
58
1
Returns: -1
87
109
18
Returns: 3
64
194
42
Returns: 6
48
105
8
Returns: 24
49
147
7
Returns: -1
146
13
130
Returns: 1
99
93
176
Returns: 2
12
40
141
Returns: 3
13
1
130
Returns: 1
94
45
104
Returns: 1
79
17
32
Returns: 1
55
103
140
Returns: 1
24
166
134
Returns: 4
17
165
190
Returns: 1
24
126
77
Returns: 4
136
71
89
Returns: 1
17
169
182
Returns: 1
192
132
173
Returns: 6
84
139
181
Returns: 1
190
32
26
Returns: 7
46
63
42
Returns: 1
77
69
96
Returns: 1
17
92
14
Returns: 2
102
108
130
Returns: 4
43
83
55
Returns: 1
119
170
125
Returns: 2
8
186
94
Returns: 3
189
129
177
Returns: 2
113
12
115
Returns: 1
118
37
194
Returns: 1
13
137
82
Returns: 1
8
43
118
Returns: 1
22
4
117
Returns: 2
127
126
139
Returns: 1
133
172
117
Returns: 3
82
72
48
Returns: 2
186
197
8
Returns: 25
151
29
40
Returns: 1
187
163
84
Returns: 1
77
80
72
Returns: 2
70
44
160
Returns: 2
103
4
2
Returns: 52
172
25
158
Returns: 1
89
103
83
Returns: 2
179
36
6
Returns: 36
96
69
29
Returns: 5
143
54
177
Returns: 1
150
156
157
Returns: 4
6
9
3
Returns: -1
128
96
1
Returns: -1
1
2
2
Returns: 1
199
200
2
Returns: 100
9
4
6
Returns: 1
34
41
7
Returns: 13
1
2
13
Returns: 1
2
8
16
Returns: 2
188
166
3
Returns: 60
2
4
6
Returns: 2
6
4
6
Returns: 3
15
12
3
Returns: -1
2
4
8
Returns: 2
10
20
30
Returns: 4
9
16
8
Returns: 3
18
12
10
Returns: 5
3
2
1
Returns: -1
125
30
17
Returns: 7
2
4
101
Returns: 2
2
4
2
Returns: -1
4
8
20
Returns: 3
11
19
5
Returns: 3
200
3
3
Returns: 101
199
200
199
Returns: 12
4
6
8
Returns: 2
6
8
11
Returns: 2
4
8
5
Returns: 3
2
10
3
Returns: 2
200
199
2
Returns: 100
8
4
20
Returns: 3
2
3
1
Returns: -1
5
3
2
Returns: 2
4
7
11
Returns: 1
2
4
4
Returns: 2
1
3
2
Returns: 1
100
200
101
Returns: 9
5
7
13
Returns: 1
200
198
7
Returns: 45
5
11
5
Returns: 5
8
16
20
Returns: 4
127
97
3
Returns: 49
32
24
8
Returns: -1
99
182
7
Returns: 36
8
4
10
Returns: 3
197
199
2
Returns: 99
4
9
5
Returns: 3
11
14
4
Returns: 3
2
1
2
Returns: 1
7
14
3
Returns: 4
128
199
3
Returns: 55
5
10
11
Returns: 2
10
5
4
Returns: 2
4
2
6
Returns: 2
6
20
7
Returns: 4
197
196
2
Returns: 99
199
197
2
Returns: 99
200
100
4
Returns: -1
4
8
100
Returns: 3
4
6
2
Returns: -1
200
168
145
Returns: 4
2
4
3
Returns: 2
143
26
99
Returns: 3
200
199
3
Returns: 67
107
194
10
Returns: 16
6
10
8
Returns: 2
16
20
6
Returns: 6
10
14
4
Returns: 6
8
4
3
Returns: 3
6
4
2
Returns: -1
79
97
17
Returns: 7
2
4
100
Returns: 2
199
198
5
Returns: 53
5
10
7
Returns: 2
186
196
21
Returns: 9
140
48
22
Returns: 12
105
140
72
Returns: 4
12
8
2
Returns: -1