ArpaKonkoori
SRM 767 · 2019-09-17 · by minimario
Problem Statement
Arpa took part in an exam called Konkoor. Here is one of questions that was on the exam:
You are given positive integers d and s. Find nonnegative integers a and b such that gcd(a, b) = d and a^2 - b^2 = s.
Given the
Constraints
- d will be between 1 and 10^12, inclusive.
- s will be between 1 and 10^12, inclusive.
5 2975 Returns: 300
There are two valid pairs (a, b): (300, 295) and (60, 25). Thus, the largest possible value of a is 300.
1 2975 Returns: 1488
This time there are four solutions. The one with the largest value a is a=1488, b=1487.
1 1000000000000 Returns: 250000000001
64 1000000000000 Returns: 7812500032
5 1000000000000 Returns: 50000000005
1 100 Returns: -1
There is no valid solution. There are some pairs (a, b) such that a^2 - b^2 = 100. However, none of them have gcd(a, b) = 1.
3 9 Returns: 3
The only solution here is a=3, b=0.
Submissions are judged against all 122 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ArpaKonkoori with a public method long long getA(long long d, long long s) · 122 test cases · 2 s / 256 MB per case