Skip to main content

Find two integers X and Y with given GCD P and given difference between their squares Q

Given two integers P and Q, the task is to find any two integers whose Greatest Common Divisor(GCD) is P and the difference between their squares is Q. If there doesn’t exist any such integers, then print “-1”.

Examples: 

Input: P = 3, Q = 27
Output:  6 3
Explanation:
Consider the two number as 6, 3. Now, the GCD(6, 3) = 3 and 6*6 – 3*3 = 27 which satisfies the condition.

Input: P = 1, Q = 100
Output: -1

 

Approach: The given problem can be solved using based on the following observations:

The given equation can also be written as:  

 

=> x^2 - y^2 = Q
=> (x + y)*(x - y) = Q  

 

Now for an integral solution of the given equation:  

 

(x+y)(x-y)  is always an integer 
=> (x+y)(x-y)  are divisors of Q 
  

 

Let  (x + y) = p1 and (x + y) = p2 
be the two equations where p1 & p2 are the divisors of Q 
such that p1 * p2 = Q.

 

Solving for the above two equation we have:  

 

=> x = \frac(p1 + p2)2 and   y = \frac(p1 - p2)2

 

From the above calculations, for x and y to be integral, then the sum of divisors must be even. Since there are 4 possible values for two values of x and y as (+x, +y), (+x, -y), (-x, +y) and (-x, -y). 
Therefore the total number of possible solution is given by 4*(count pairs of divisors with even sum).

 

Now among these pairs, find the pair with GCD as P and print the pair. If no such pair exists, print -1.

 

Below is the implementation of the above approach:

 

C++




// C++ program for the above approach
 
#include
using namespace std;
 
// Function to print a valid pair with
// the given criteria
int printValidPair(int P, int Q)
 
    // Iterate over the divisors of Q
    for (int i = 1; i * i <= Q; i++)
 
        // check if Q is a multiple of i
        if (Q % i == 0)
 
            // L = (A - B) <- 1st equation
            // R = (A + B) <- 2nd equation
            int L = i;
            int R = Q / i;
 
            // Calculate value of A
            int A = (L + R) / 2;
 
            // Calculate value of B
            int B = (R - L) / 2;
 
            // As A and B both are integers
            // so the parity of L and R
            // should be the same
            if (L % 2 != R % 2)
                continue;
            
 
            // Check the first condition
            if (__gcd(A, B) == P)
                cout << A << " " << B;
                return 0;
            
        
    
 
    // If no such A, B exist
    cout << -1;
 
    return 0;
 
// Driver Code
int main()
    int P = 3, Q = 27;
    printValidPair(P, Q);
 
    return 0;
 















Java

















 






 




 



























// Java program for the above approach


import java.util.*;


 


class GFG


 


// Function to print a valid pair with


// the given criteria


static int printValidPair(int P, int Q)




 


    // Iterate over the divisors of Q


    for (int i = 1; i * i <= Q; i++) 


 


        // check if Q is a multiple of i


        if (Q % i == 0) 


 


            // L = (A - B) <- 1st equation


            // R = (A + B) <- 2nd equation


            int L = i;


            int R = Q / i;


 


            // Calculate value of A


            int A = (L + R) / 2;


 


            // Calculate value of B


            int B = (R - L) / 2;


 


            // As A and B both are integers


            // so the parity of L and R


            // should be the same


            if (L % 2 != R % 2) 


                continue;


            


 


            // Check the first condition


            if (__gcd(A, B) == P) 


                System.out.print(A+ " " +  B);


                return 0;


            


        


    


 


    // If no such A, B exist


    System.out.print(-1);


    return 0;


 




static int __gcd(int a, int b)  


  


    return b == 0? a:__gcd(b, a % b);     




   


// Driver Code


public static void main(String[] args)




    int P = 3, Q = 27;


    printValidPair(P, Q);






 


// This code is contributed by 29AjayKumar






































Python3

















 






 




 



























# python program for the above approach


import math


 


# Function to print a valid pair with


# the given criteria


def printValidPair(P, Q):


 


    # Iterate over the divisors of Q


    for i in range(1, int(math.sqrt(Q)) + 1):


 


        # check if Q is a multiple of i


        if (Q % i == 0):


 


            # L = (A - B) <- 1st equation


            # R = (A + B) <- 2nd equation


            L = i


            R = Q // i


 


            # Calculate value of A


            A = (L + R) // 2


 


            # Calculate value of B


            B = (R - L) // 2


 


            # As A and B both are integers


            # so the parity of L and R


            # should be the same


            if (L % 2 != R % 2):


                continue


 


            # Check the first condition


            if (math.gcd(A, B) == P):


                print(f"A B")


                return 0


 


    # If no such A, B exist


    print(-1)


 


    return 0


 


# Driver Code


if __name__ == "__main__":


 


    P = 3


    Q = 27


    printValidPair(P, Q)


 


    # This code is contributed by rakeshsahni






































C#

















 






 




 



























// C# program for the above approach


using System;


class GFG




 


    // Function to print a valid pair with


    // the given criteria


    static int printValidPair(int P, int Q)


    


 


        // Iterate over the divisors of Q


        for (int i = 1; i * i <= Q; i++)


        


 


            // check if Q is a multiple of i


            if (Q % i == 0)


            


 


                // L = (A - B) <- 1st equation


                // R = (A + B) <- 2nd equation


                int L = i;


                int R = Q / i;


 


                // Calculate value of A


                int A = (L + R) / 2;


 


                // Calculate value of B


                int B = (R - L) / 2;


 


                // As A and B both are integers


                // so the parity of L and R


                // should be the same


                if (L % 2 != R % 2)


                


                    continue;


                


 


                // Check the first condition


                if (__gcd(A, B) == P)


                


                    Console.Write(A + " " + B);


                    return 0;


                


            


        


 


        // If no such A, B exist


        Console.Write(-1);


        return 0;


 


    


    static int __gcd(int a, int b)


    


        return b == 0 ? a : __gcd(b, a % b);


    


 


    // Driver Code


    public static void Main()


    


        int P = 3, Q = 27;


        printValidPair(P, Q);


    




 


// This code is contributed by gfgking






































Javascript

















 






 




 



































































 
 


Output: 

6 3


 




 


Time Complexity: O(sqrt(Q))
Auxiliary Space: O(1)


 








                                            Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.

                                            Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!







 

https://neveropen.tech/find-two-integers-x-and-y-with-given-gcd-p-and-given-difference-between-their-squares-q/?feed_id=28&_unique_id=683cb79516b8d












Labels:





























Comments











Post a Comment



















Popular posts from this blog





















Bare Metal Billing Client Portal Guide




























      Contents   Order a Bare Metal Server  My Custom / Contract Pricing   View Contract Details   Location Management      Order History & Status   View Order Details         Introduction  The phoenixNAP Client Portal allows you to purchase bare metal servers  and other phoenixNAP products and services. Using the intuitive interface and its essential tools, you can also easily manage your infrastructure.  This quick guide will show you how to use the new form  to order a bare metal server and how to navigate through new bare metal features  within the phoenixNAP Client Portal.     Order a Bare Metal Server  An order form is an accordion-based process for purchasing phoenixNAP products. Our order form allows you to view the pricing and order multiple products from the same category at the same time.     Note:  The prices on the form are per month . A contract is not required. However, if you want a contracted price, you may be eligible for a discount  depending on the quantity and ...




















Post a Comment









Read more






























Add an element in Array  to make the bitwise XOR as K




























   Given an array arr[]  containing N positive integers, the task is to add an integer such that the bitwise Xor of the new array becomes K.  Examples:    Input: arr[] = 1, 4, 5, 6, K = 4 Output: 2 Explanation: Bit-wise XOR of the array is 6.  And bit-wise XOR of 6 and 2 is 4.  Input: arr[] = 2, 7, 9, 1, K = 5 Output:  8        Approach: The solution to the problem is based on the following idea of bitwise Xor:   If for two numbers X  and Y , the bitwise Xor of X and Y is Z  then the bitwise Xor of X and Z is Y.   Follow the steps to solve the problem:   Let the bitwise XOR of the array elements be X .   Say the required value to be added is Y  such that X Xor Y = K .  From the above observation, it is clear that the value to be added (Y) is the same as X Xor K .   Below is the implementation of the above approach:   C++                                 // C++ code to implement the above approach     #include  using  namespace  std;     // Function to find the required value  int  find_...




















Post a Comment









Read more






























Mahotas – Template Matching




























   In this article we will see how we can do template matching in mahotas. Template is basically a part or structure of image. In this tutorial we will use “lena” image, below is the command to load it.    mahotas.demos.load('lena')  Below is the lena image             In order to do this we will use mahotas.template_match method Syntax :  mahotas.template_match(img, template) Argument :  It takes image object and template as argument Return :  It returns image object      Note :  Input image should be filtered or should be loaded as grey In order to filter the image we will take the image object which is numpy.ndarray and filter it with the help of indexing, below is the command to do this    image = image[:, :, 0]  Below is the implementation        Python3                                 # importing required libraries  import  mahotas  import  mahotas.demos  from  pylab import  gray, imshow, show  import  numpy as np  import  matplotlib.pyplot as plt        # loading image  ...




















Post a Comment









Read more