TheEquation | Topcoder Archive

Problem Statement

You are given three positive integers, X, Y and P. Return the least sum of two positive integers a and b such that P is a divisor of a*X+b*Y.

Definition

Class:: TheEquation
Method:: leastSum
Parameters:: int, int, int
Returns:: int
Method signature:: int leastSum(int X, int Y, int P)
(be sure your method is public)

Notes

The answer is never greater than 2*P: if a = P and b = P, then P is definitely a divisor of a*X+b*Y.

Constraints

X, Y and P will each be between 1 and 1000, inclusive.

Examples

```
2
```
```
6
```
```
5
```
```
Returns: 3
```
When a=2 and b=1, a*X+b*Y is 10, which is a multiple of P=5. No other valid pair of values for a and b has a smaller sum.
```
5
```
```
5
```
```
5
```
```
Returns: 2
```
Don't forget that a and b must be positive.
```
998
```
```
999
```
```
1000
```
```
Returns: 501
```
```
1
```
```
1
```
```
1000
```
```
Returns: 1000
```
```
347
```
```
873
```
```
1000
```
```
Returns: 34
```

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.