Find two Integers whose GCD is A, and the Difference Between their Squares is B

Prerequisite: GCD

Problem

Given two positive integers, A and B. Find two integers X, Y whose Greatest Common Divisor is A, and the difference between their squares is B. Print "-1" if no such pair exists. You can print any one pair if multiple pairs are possible.

Input: Two positive integers A and B.

Output: Print X and Y if the pair exists or print "-1". Print the larger integer first.

For example,

1.
Input: A = 4, B = 80
Output: 12 8
Explanation: GCD of 12 and 8 is 4, and the difference between their squares is 80. i.e., 144 - 64 = 80.

2.
Input: A = 1, B = 24
Output: 7 5
Explanation: GCD of 7 and 5 is 1, and the difference between their squares is 24. i.e., 49 - 25 = 24.

3.
Input: A = 4, B = 20
Output: -1
Explanation: No such pair exists.

Alert Ninjas:  Don’t stop now! Enroll in the Competitive Programming course today. Learn the art of writing time and space-efficient code and compete in code competitions worldwide. 

Recommended: Please try to solve it yourself before moving on to the solution.

Solution

1. Let the final two integers be x and y.
2. According to the problem, x² - y² = B and x² - y² = (x-y)*(x+y). Therefore, (x+y)*(x-y) = B.
3. Now x, y, and B are integers, therefore (x+y), (x-y) must be an integer, and (x+y) and (x-y) must be divisors of B.
4. Let x+y = P and x-y = Q. 
5. Therefore, x = (P+Q)/2 and y = (P-Q)/2. 
6. For x and y to be integers, the parity of P and Q must be the same.
7. Since there are four possible pairs of x and y as (+x, +y), (-x, -y), (+x, -y), and (-x, +y). Therefore, the number of possible solutions is 4*(count pairs of divisors with even sum).
8. Now we have to find any of those 4 pairs whose gcd is A.

C++

#include <bits/stdc++.h>
using namespace std;

// Function to find the pairs x and y with given gcd A and difference between their squares B.
void findPairs(int A, int B)
{
    // Iterate over the divisors of B to find x and y.
    for (int i = 1; i * i <= B; i++) {

    // check if i is a factor of B.
        if (B % i == 0) {
    
            // P = (x+y), first divisor of B.
            // Q = (x-y), second divisor of B.
            int P = i;
            int Q = B / i;

              // As P and Q are integers, their parity must be the same.
            if (P % 2 != Q % 2) {
                continue;
            }

            // x = (P+Q)/2.
            // y = (P-Q)/2.
            int x = (P + Q) / 2;
            int y = (Q - P) / 2;

            // if gcd of x, y is A, the pair (x,y) is valid.
            if (__gcd(x, y) == A) {
                cout << x << " " << y;
                return;
            }
        }
    }
    // Print -1 is no such pair exists.
    cout << -1;
    return;
}

int main()
{
    int A = 4, B = 80;
    findPairs(A, B);
    return 0;
}

Input: A = 4, B = 80

Output: 

12 8

Time Complexity: O(√ B), where B is the given difference between squares of X and Y.

Space Complexity: O(1).