Dados dos enteros X e Y , la tarea es encontrar el número de enteros, K , tal que mcd(X, Y) sea igual a mcd(X+K, Y) , donde 0 < K <Y .
Ejemplos:
Entrada: X = 3, Y = 15
Salida: 4
Explicación: Todos los valores posibles de K son {0, 3, 6, 9} para los cuales MCD (X, Y) = MCD (X + K, Y).Entrada: X = 2, Y = 12
Salida: 2
Explicación: Todos los valores posibles de K son {0, 8}.
Enfoque ingenuo: el enfoque más simple para resolver el problema es iterar sobre el rango [0, Y – 1] y para cada valor de i , verificar si GCD (X + i, Y) es igual a GCD (X, Y) o no.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
4
Complejidad temporal: O(YlogY)
Espacio auxiliar: O(1)
Enfoque Eficiente: La idea es utilizar el concepto de función de totiente de Euler . Siga los pasos a continuación para resolver el problema:
- Calcule el gcd de X e Y y guárdelo en una variable g .
- Inicialice una variable n con Y/g .
- Ahora, encuentre la función totient para n , que será la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
4
Complejidad de tiempo: O(log(min(X, Y)) + √N) donde N es Y/gcd(X, Y).
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA