Find GCD between the sum of two given integers raised to the power of N and their difference
Given three positive integers, P, Q and N, the task is to find the GCD of (PN + QN) and (P – Q) under modulo 109 + 7.
Examples:
Input: p = 10, q = 6, n = 5
Output: 4
Explanation: pn + qn = 105 + 65 = 107776 and p – q = 4. GCD of 107776 and 4 is 4.Input: p = 7, q = 2 and n = 5
Output: 1
Explanation: pn + qn = 75 + 25 = 16839 and p – q = 5. GCD of 16839 and 5 is 1.
Approach: Since the number (pn + qn) can be extremely large, such a huge number cannot be stored in any data type and thus GCD cannot be calculated using the Euclidean algorithm. Therefore, modular arithmetic can be used to find the answer.
Follow the below steps to solve this problem:
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> #define mod 1000000007 using namespace std; // Function to find the value of (a ^ n) % d long long int power( long long a, long long n, long long int d) { // Stores the value // of (a ^ n) % d long long int res = 1; // Calculate the value // of (a ^ n) % d while (n) { // If n is odd if (n % 2) { // Update res res = ((res % d) * (a % d)) % d; } // Update a a = ((a % d) * (a % d)) % d; // Update n n /= 2; } return res; } // Function to find the GCD of (p ^ n + q ^ n) // and p - q mod d long long int gcd( long long p, long long q, long long n) { // If p and q are equal if (p == q) { return (power(p, n, mod) + power(q, n, mod)) % mod; } // Stores GCD of (p ^ n + q ^ n) // and (p - q) mod d long long int candidate = 1; // Stores the value of (p-q) long long int num = p - q; // Stores square root of num long long int sq = sqrt (num); // Find the divisors of num. for ( long long i = 1; i <= sq; ++i) { // If i divides num if (num % i == 0) { // Stores power of (p ^ n) mod i long long int X = power(p, n, i); // Stores power of (q ^ n) mod i long long int Y = power(q, n, i); // Stores power of (p ^ n + q ^ n) mod i long long int temp = (X + Y) % i; // If (p^n + q^n) is divisible by i if (temp == 0) { // Calculate the largest divisor. candidate = max(candidate, i); } // If i divides num, (num/i) also divides // num. Hence, calculate temp. temp = (power(p, n, num / i) + power(q, n, num / i)) % (num / i); // If (p^n + q^n) is divisible // by (num/i) if (temp == 0) { // Calculate the largest divisor. candidate = max(candidate, num / i); } } } return candidate % mod; } // Driver Code int main() { // Given p, q and n long long int p, q, n; p = 10; q = 6; n = 5; // Function Call cout << gcd(p, q, n); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { static int mod = 1000000007 ; // Function to find the value of (a ^ n) % d static int power( int a, int n, int d) { // Stores the value // of (a ^ n) % d int res = 1 ; // Calculate the value // of (a ^ n) % d while (n != 0 ) { // If n is odd if ((n % 2 ) != 0 ) { // Update res res = ((res % d) * (a % d)) % d; } // Update a a = ((a % d) * (a % d)) % d; // Update n n /= 2 ; } return res; } // Function to find the GCD of (p ^ n + q ^ n) // and p - q mod d static int gcd( int p, int q, int n) { // If p and q are equal if (p == q) { return (power(p, n, mod) + power(q, n, mod)) % mod; } // Stores GCD of (p ^ n + q ^ n) // and (p - q) mod d int candidate = 1 ; // Stores the value of (p-q) int num = p - q; // Stores square root of num int sq = ( int )Math.sqrt(num); // Find the divisors of num. for ( int i = 1 ; i <= sq; ++i) { // If i divides num if (num % i == 0 ) { // Stores power of (p ^ n) mod i int X = power(p, n, i); // Stores power of (q ^ n) mod i int Y = power(q, n, i); // Stores power of (p ^ n + q ^ n) mod i int temp = (X + Y) % i; // If (p^n + q^n) is divisible by i if (temp == 0 ) { // Calculate the largest divisor. candidate = Math.max(candidate, i); } // If i divides num, (num/i) also divides // num. Hence, calculate temp. temp = (power(p, n, num / i) + power(q, n, num / i)) % (num / i); // If (p^n + q^n) is divisible // by (num/i) if (temp == 0 ) { // Calculate the largest divisor. candidate = Math.max(candidate, num / i); } } } return candidate % mod; } // Driver code public static void main(String[] args) { // Given p, q and n int p, q, n; p = 10 ; q = 6 ; n = 5 ; // Function Call System.out.println(gcd(p, q, n)); } } // This code is contributed by code_hunt. |
Python3
# Python program for the above approach import math mod = 1000000007 ; # Function to find the value of (a ^ n) % d def power(a, n, d): # Stores the value # of (a ^ n) % d res = 1 ; # Calculate the value # of (a ^ n) % d while (n ! = 0 ): # If n is odd if ((n % 2 ) ! = 0 ): # Update res res = ((res % d) * (a % d)) % d; # Update a a = ((a % d) * (a % d)) % d; # Update n n / = 2 ; return res; # Function to find the GCD of (p ^ n + q ^ n) # and p - q mod d def gcd(p, q, n): # If p and q are equal if (p = = q): return (power(p, n, mod) + power(q, n, mod)) % mod; # Stores GCD of (p ^ n + q ^ n) # and (p - q) mod d candidate = 1 ; # Stores the value of (p-q) num = p - q; # Stores square root of num sq = ( int )(math.sqrt(num)); # Find the divisors of num. for i in range ( 1 , sq): # If i divides num if (num % i = = 0 ): # Stores power of (p ^ n) mod i X = power(p, n, i); # Stores power of (q ^ n) mod i Y = power(q, n, i); # Stores power of (p ^ n + q ^ n) mod i temp = (X + Y) % i; # If (p^n + q^n) is divisible by i if (temp = = 0 ): # Calculate the largest divisor. candidate = max (candidate, i); # If i divides num, (num/i) also divides # num. Hence, calculate temp. temp = (power(p, n, num / i) + power(q, n, num / i)) % (num / i); # If (p^n + q^n) is divisible # by (num/i) if (temp = = 0 ): # Calculate the largest divisor. candidate = max (candidate, num / i); return candidate % mod; # Driver code if __name__ = = '__main__' : # Given p, q and n p = 10 ; q = 6 ; n = 5 ; # Function Call print (( int )(gcd(p, q, n))); # This code contributed by aashish1995 |
C#
// C# program for the above approach using System; class GFG { static int mod = 1000000007; // Function to find the value of (a ^ n) % d static int power( int a, int n, int d) { // Stores the value // of (a ^ n) % d int res = 1; // Calculate the value // of (a ^ n) % d while (n != 0) { // If n is odd if ((n % 2) != 0) { // Update res res = ((res % d) * (a % d)) % d; } // Update a a = ((a % d) * (a % d)) % d; // Update n n /= 2; } return res; } // Function to find the GCD of (p ^ n + q ^ n) // and p - q mod d static int gcd( int p, int q, int n) { // If p and q are equal if (p == q) { return (power(p, n, mod) + power(q, n, mod)) % mod; } // Stores GCD of (p ^ n + q ^ n) // and (p - q) mod d int candidate = 1; // Stores the value of (p-q) int num = p - q; // Stores square root of num int sq = ( int )Math.Sqrt(num); // Find the divisors of num. for ( int i = 1; i <= sq; ++i) { // If i divides num if (num % i == 0) { // Stores power of (p ^ n) mod i int X = power(p, n, i); // Stores power of (q ^ n) mod i int Y = power(q, n, i); // Stores power of (p ^ n + q ^ n) mod i int temp = (X + Y) % i; // If (p^n + q^n) is divisible by i if (temp == 0) { // Calculate the largest divisor. candidate = Math.Max(candidate, i); } // If i divides num, (num/i) also divides // num. Hence, calculate temp. temp = (power(p, n, num / i) + power(q, n, num / i)) % (num / i); // If (p^n + q^n) is divisible // by (num/i) if (temp == 0) { // Calculate the largest divisor. candidate = Math.Max(candidate, num / i); } } } return candidate % mod; } // Driver code static public void Main() { // Given p, q and n int p, q, n; p = 10; q = 6; n = 5; // Function Call Console.WriteLine(gcd(p, q, n)); } } // This is contributed by Dharanendra L V |
Javascript
<script> // javascript program for the above approach const mod = 1000000007; // Function to find the value of (a ^ n) % d function power(a , n , d) { // Stores the value // of (a ^ n) % d var res = 1; // Calculate the value // of (a ^ n) % d while (n != 0) { // If n is odd if ((n % 2) != 0) { // Update res res = ((res % d) * (a % d)) % d; } // Update a a = ((a % d) * (a % d)) % d; // Update n n /= 2; } return res; } // Function to find the GCD of (p ^ n + q ^ n) // and p - q mod d function gcd(p , q , n) { // If p and q are equal if (p == q) { return (power(p, n, mod) + power(q, n, mod)) % mod; } // Stores GCD of (p ^ n + q ^ n) // and (p - q) mod d var candidate = 1; // Stores the value of (p-q) var num = p - q; // Stores square root of num var sq = parseInt( Math.sqrt(num)); // Find the divisors of num. for (i = 1; i <= sq; ++i) { // If i divides num if (num % i == 0) { // Stores power of (p ^ n) mod i var X = power(p, n, i); // Stores power of (q ^ n) mod i var Y = power(q, n, i); // Stores power of (p ^ n + q ^ n) mod i var temp = (X + Y) % i; // If (p^n + q^n) is divisible by i if (temp == 0) { // Calculate the largest divisor. candidate = Math.max(candidate, i); } // If i divides num, (num/i) also divides // num. Hence, calculate temp. temp = (power(p, n, num / i) + power(q, n, num / i)) % (num / i); // If (p^n + q^n) is divisible // by (num/i) if (temp == 0) { // Calculate the largest divisor. candidate = Math.max(candidate, num / i); } } } return candidate % mod; } // Driver code // Given p, q and n var p, q, n; p = 10; q = 6; n = 5; // Function Call document.write(gcd(p, q, n)); // This code is contributed by todaysgaurav </script> |
4
Time Complexity: O(sqrt(p – q))
Auxiliary Space: O(1)
Contact Us