Contar números hasta C que se pueden reducir a 0 sumando o restando A o B

Dados tres enteros no negativos A , B y C , la tarea es contar los números en el rango [1, C] que se pueden reducir a 0 sumando o restando A o B .

Ejemplos:

Entrada: A = 2, B = 4, C = 7
Salida: 3
Explicación: Los números del rango [1, 7] que pueden reducirse a 0 mediante operaciones dadas son:

1. Para el elemento 2: El número se puede modificar como 2 – 2 = 0.
2. Para el elemento 4: El número se puede modificar como 4 – 2 – 2 = 0.
3. Para el elemento 6: El número se puede modificar como 6 – 4 – 2 = 0.

Por lo tanto, la cuenta total es 3.

Entrada: A = 2, B = 3, C = 5
Salida: 5

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:

• Considere X e Y el número de sumas o restas de A y B que se realizan respectivamente.
• Después de aplicar las operaciones sobre cualquier número N , se convierte en Ax + By . Por lo tanto, por el Algoritmo de Euclides Extendido , se puede decir que existen coeficientes enteros x e y tales que Ax + By = GCD(A, B) .
• Por lo tanto, N debe ser un múltiplo de MCD(A, B) , digamos G . Ahora el problema se reduce a encontrar el número de múltiplos de G que están en el rango [1, C] que es piso (C/G) .

Siga los pasos a continuación para resolver el problema:

• Encuentre el MCD de A y B y guárdelo en una variable, digamos G .
• Ahora, el conteo de números sobre el rango [1, C] son ​​los múltiplos de G que tienen valores como máximo C , que viene dado por el piso (C/G) .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate GCD of the
// two numbers a and b
long long gcd(long long a, long long b)
{
    // Base Case
    if (b == 0)
        return a;
 
    // Recursively find the GCD
    return gcd(b, a % b);
}
 
// Function to count the numbers up
// to C that can be reduced to 0 by
// adding or subtracting A or B
void countDistinctNumbers(long long A,
                          long long B,
                          long long C)
{
    // Stores GCD of A and B
    long long g = gcd(A, B);
 
    // Stores the count of multiples
    // of g in the range (0, C]
    long long count = C / g;
 
    // Print the result
    cout << count;
}
 
 
// Driver Code
int main()
{
    long long A = 2, B = 3, C = 5;
    countDistinctNumbers(A, B, C);
 
    return 0;
}

// Java program for the above approach
class GFG{
 
// Function to calculate GCD of the
// two numbers a and b
static long gcd(long a, long b)
{
     
    // Base Case
    if (b == 0)
        return a;
 
    // Recursively find the GCD
    return gcd(b, a % b);
}
 
// Function to count the numbers up
// to C that can be reduced to 0 by
// adding or subtracting A or B
static void countDistinctNumbers(long A, long B,
                                 long C)
{
     
    // Stores GCD of A and B
    long g = gcd(A, B);
 
    // Stores the count of multiples
    // of g in the range (0, C]
    long count = C / g;
 
    // Print the result
    System.out.println(count);
}
 
// Driver Code
public static void main(String[] args)
{
    long A = 2, B = 3, C = 5;
     
    countDistinctNumbers(A, B, C);
}
}
 
// This code is contributed by abhinavjain194

# Python3 program for the above approach
 
# Function to calculate GCD of the
# two numbers a and b
def gcd(a, b):
     
    # Base Case
    if (b == 0):
        return a
         
    # Recursively find the GCD
    return gcd(b, a % b)
 
# Function to count the numbers up
# to C that can be reduced to 0 by
# adding or subtracting A or B
def countDistinctNumbers(A, B, C):
     
    # Stores GCD of A and B
    g = gcd(A, B)
     
    # Stores the count of multiples
    # of g in the range (0, C]
    count = C // g
  
    # Print the result
    print(count)
 
# Driver code
A = 2
B = 3
C = 5
 
countDistinctNumbers(A, B, C)
 
# This code is contributed by abhinavjain194

// C# program for the above approach
using System;
 
class GFG{
     
// Function to calculate GCD of the
// two numbers a and b
static long gcd(long a, long b)
{
     
    // Base Case
    if (b == 0)
        return a;
 
    // Recursively find the GCD
    return gcd(b, a % b);
}
 
// Function to count the numbers up
// to C that can be reduced to 0 by
// adding or subtracting A or B
static void countDistinctNumbers(long A, long B,
                                 long C)
{
     
    // Stores GCD of A and B
    long g = gcd(A, B);
 
    // Stores the count of multiples
    // of g in the range (0, C]
    long count = C / g;
 
    // Print the result
    Console.Write(count);
}
 
// Driver Code
static void Main()
{
    long A = 2, B = 3, C = 5;
    countDistinctNumbers(A, B, C);
}
}
 
// This code is contributed by abhinavjain194

<script>
 
// Javascript program for the above approach
 
// Function to calculate GCD of the
// two numbers a and b
function gcd(a, b)
{
    // Base Case
    if (b == 0)
        return a;
 
    // Recursively find the GCD
    return gcd(b, a % b);
}
 
// Function to count the numbers up
// to C that can be reduced to 0 by
// adding or subtracting A or B
function countDistinctNumbers(A, B, C)
{
    // Stores GCD of A and B
    var g = gcd(A, B);
 
    // Stores the count of multiples
    // of g in the range (0, C]
    var count = C / g;
 
    // Print the result
    document.write(count);
}
 
// Driver Code
    var A = 2, B = 3, C = 5;
    countDistinctNumbers(A, B, C);
 
// This code is contributed by ipg2016107.
</script>

5

Complejidad de tiempo: O(log(min(A, B))) 
Espacio auxiliar: O(1)