TheEquation
SRM 373 · 2007-10-23 · by Vedensky
SRM 373 · 2007-10-23 · by Vedensky · Brute Force
Problem Statement
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.
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
0)
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.
1)
5 5 5 Returns: 2
Don't forget that a and b must be positive.
2)
998 999 1000 Returns: 501
3)
1 1 1000 Returns: 1000
4)
1000 1000 999 Returns: 999
Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TheEquation with a public method int leastSum(int X, int Y, int P) · 69 test cases · 2 s / 256 MB per case