Count all possible values of K less than Y such that GCD(X, Y) = GCD(X+K, Y)
Given two integers X and Y, the task is to find the number of integers, K, such that gcd(X, Y) is equal to gcd(X+K, Y), where 0 < K <Y.
Examples:
Input: X = 3, Y = 15
Output: 4
Explanation: All possible values of K are {0, 3, 6, 9} for which GCD(X, Y) = GCD(X + K, Y).Input: X = 2, Y = 12
Output: 2
Explanation: All possible values of K are {0, 8}.
Naive Approach: The simplest approach to solve the problem is to iterate over the range [0, Y – 1]and for each value of i, check if GCD(X + i, Y) is equal to GCD(X, Y) or not.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to calculate // GCD of two integers int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to count possible // values of K int calculateK( int x, int y) { int count = 0; int gcd_xy = gcd(x, y); for ( int i = 0; i < y; i++) { // If required condition // is satisfied if (gcd(x + i, y) == gcd_xy) // Increase count count++; } return count; } // Driver Code int main() { // Given X and y int x = 3, y = 15; cout << calculateK(x, y) << endl; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to calculate // GCD of two integers static int gcd( int a, int b) { if (b == 0 ) return a; return gcd(b, a % b); } // Function to count possible // values of K static int calculateK( int x, int y) { int count = 0 ; int gcd_xy = gcd(x, y); for ( int i = 0 ; i < y; i++) { // If required condition // is satisfied if (gcd(x + i, y) == gcd_xy) // Increase count count++; } return count; } // Driver code public static void main(String[] args) { // Given X and y int x = 3 , y = 15 ; System.out.print(calculateK(x, y)); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Function to calculate # GCD of two integers def gcd(a, b): if (b = = 0 ): return a return gcd(b, a % b) # Function to count possible # values of K def calculateK(x, y): count = 0 gcd_xy = gcd(x, y) for i in range (y): # If required condition # is satisfied if (gcd(x + i, y) = = gcd_xy): # Increase count count + = 1 return count # Driver Code if __name__ = = '__main__' : # Given X and y x = 3 y = 15 print (calculateK(x, y)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG{ // Function to calculate // GCD of two integers static int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to count possible // values of K static int calculateK( int x, int y) { int count = 0; int gcd_xy = gcd(x, y); for ( int i = 0; i < y; i++) { // If required condition // is satisfied if (gcd(x + i, y) == gcd_xy) // Increase count count++; } return count; } // Driver code public static void Main(String[] args) { // Given X and y int x = 3, y = 15; Console.Write(calculateK(x, y)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the above approach // Function to calculate // GCD of two integers function gcd(a , b) { if (b == 0) return a; return gcd(b, a % b); } // Function to count possible // values of K function calculateK(x , y) { var count = 0; var gcd_xy = gcd(x, y); for (i = 0; i < y; i++) { // If required condition // is satisfied if (gcd(x + i, y) == gcd_xy) // Increase count count++; } return count; } // Driver code // Given X and y var x = 3, y = 15; document.write(calculateK(x, y)); // This code is contributed by todaysgaurav </script> |
4
Time Complexity: O(YlogY)
Auxiliary Space: O(1)
Efficient Approach: The idea is to use the concept of Euler’s totient function. Follow the steps below to solve the problem:
- Calculate the gcd of X and Y and store it in a variable g.
- Initialize a variable n with Y/g.
- Now, find the totient function for n which will be the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to find the gcd of a and b int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find the number of Ks int calculateK( int x, int y) { // Find gcd int g = gcd(x, y); int n = y / g; int res = n; // Calculating value of totient // function for n for ( int i = 2; i * i <= n; i++) { if (n % i == 0) { res -= (res / i); while (n % i == 0) n /= i; } } if (n != 1) res -= (res / n); return res; } // Driver Code int main() { // Given X and Y int x = 3, y = 15; cout << calculateK(x, y) << endl; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the gcd of a and b static int gcd( int a, int b) { if (b == 0 ) return a; return gcd(b, a % b); } // Function to find the number of Ks static int calculateK( int x, int y) { // Find gcd int g = gcd(x, y); int n = y / g; int res = n; // Calculating value of totient // function for n for ( int i = 2 ; i * i <= n; i++) { if (n % i == 0 ) { res -= (res / i); while (n % i == 0 ) n /= i; } } if (n != 1 ) res -= (res / n); return res; } // Driver Code public static void main(String[] args) { // Given X and Y int x = 3 , y = 15 ; System.out.print(calculateK(x, y) + "\n" ); } } // This code is contributed by shikhasingrajput |
Python3
# Python 3 program for the above approach # Function to find the gcd of a and b def gcd(a, b): if (b = = 0 ): return a return gcd(b, a % b) # Function to find the number of Ks def calculateK(x, y): # Find gcd g = gcd(x, y) n = y / / g res = n # Calculating value of totient # function for n i = 2 while i * i < = n: if (n % i = = 0 ): res - = (res / / i) while (n % i = = 0 ): n / / = i i + = 1 if (n ! = 1 ): res - = (res / / n) return res # Driver Code if __name__ = = "__main__" : # Given X and Y x = 3 y = 15 print (calculateK(x, y)) # This code is contributed by chitranayal. |
C#
// C# program for the above approach using System; class GFG{ // Function to find the gcd of a and b static int gcd( int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find the number of Ks static int calculateK( int x, int y) { // Find gcd int g = gcd(x, y); int n = y / g; int res = n; // Calculating value of totient // function for n for ( int i = 2; i * i <= n; i++) { if (n % i == 0) { res -= (res / i); while (n % i == 0) n /= i; } } if (n != 1) res -= (res / n); return res; } // Driver Code public static void Main(String[] args) { // Given X and Y int x = 3, y = 15; Console.Write(calculateK(x, y) + "\n" ); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // javascript program for the above approach // Function to find the gcd of a and b function gcd(a , b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find the number of Ks function calculateK(x , y) { // Find gcd var g = gcd(x, y); var n = y / g; var res = n; // Calculating value of totient // function for n for (i = 2; i * i <= n; i++) { if (n % i == 0) { res -= (res / i); while (n % i == 0) n /= i; } } if (n != 1) res -= (res / n); return res; } // Driver Code // Given X and Y var x = 3, y = 15; document.write(calculateK(x, y) + "\n" ); // This code is contributed by umadevi9616 </script> |
4
Time Complexity: O(log(min(X, Y)) + ?N) where N is Y/gcd(X, Y).
Auxiliary Space: O(1)