ArpaKonkoori | Topcoder Archive

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 longs d and s, compute and return the largest possible value of a. If there is no solution, return -1 instead.

Definition

Class:: ArpaKonkoori
Method:: getA
Parameters:: long, long
Returns:: long
Method signature:: long getA(long d, long s)
(be sure your method is public)

Constraints

d will be between 1 and 10^12, inclusive.
s will be between 1 and 10^12, inclusive.

Examples

```
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
```
```
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.
```
12345678901
```
```
345
```
```
Returns: -1
```
```
3
```
```
9
```
```
Returns: 3
```
The only solution here is a=3, b=0.

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.