Encuentre el conteo de números de 0 a n que satisfaga la ecuación dada para un valor K

Dados tres números enteros positivos a, b y n , nuestra tarea es encontrar el recuento total de todos los números K que van de 0 a n que satisfacen la ecuación dada (( k % a ) % b) = (( k % b ) % a)
Ejemplos:
 

Entrada: a = 3, b = 4, n = 25 
Salida: 10 
Explicación: 
Los valores que satisfacen la ecuación anterior son 0 1 2 3 12 13 14 15 24 25. Por ejemplo, para K = 13; ((13 % 3) % 4) da 1 y ((13 % 4) % 3) también da 1 como salida. 
Entrada: a = 1, b = 13, n = 500 
Salida: 501 
Explicación: 
En total hay 501 números entre 0 y 500 que satisfacen la ecuación dada. 
 

Enfoque:
para resolver el problema mencionado anteriormente, tenemos la condición dada (( k % a ) % b) = (( k % b ) % a) que siempre se cumplirá para los números de 0 a max(a, b) – 1 . Entonces, de acuerdo con la declaración proporcionada anteriormente, si tenemos a <= b, verifique todos los números de 0 a b-1 y tenemos los siguientes dos casos: 
 

• Calculamos (k % a) % b, en este caso la respuesta siempre será (k % a) ya que el valor de (k % a) siempre será menor que b.
• Calculamos (k % b) % a, en este caso también la respuesta siempre será (k % a) porque (k % b) devolverá k como k es menor que b.

De manera similar, podemos verificar los casos para a > b. Entonces, ahora debemos verificar todos los números que son divisibles tanto por a como por b en el rango de 0 a n. Esto se puede encontrar con la ayuda de MCM de a y b. Entonces, ahora podemos encontrar fácilmente el número de múltiplos del MCM en el rango de 0 an al sumergir n en MCM. Agregaremos 1 a los múltiplos para incluir 0 como múltiplo. Y luego tenemos que multiplicar el número de múltiplos por max(a, b) para que podamos encontrar todos los números que satisfagan la condición dada. Pero si la suma del último múltiplo y max(a, b) excede nuestro rango de n números, entonces debemos excluir los números adicionales.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation to Find the total
// count of all the numbers from 0 to n which
// satisfies the given equation for a value K
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the values
int findAns(int a, int b, int n)
{
    // Calculate the LCM
    int lcm = (a * b) / __gcd(a, b);
 
    // Calculate the multiples of lcm
    int multiples = (n / lcm) + 1;
 
    // Find the values which satisfies
    // the given condition
    int answer = max(a, b) * multiples;
 
    // Subtract the extra values
    int lastvalue = lcm * (n / lcm) + max(a, b);
 
    if (lastvalue > n)
        answer = answer - (lastvalue - n - 1);
 
    // Return the final result
    return answer;
}
 
// Driver code
int main()
{
    int a = 1, b = 13, n = 500;
 
    cout << findAns(a, b, n) << endl;
}

// Java implementation to find the total
// count of all the numbers from 0 to n which
// satisfies the given equation for a value K
class GFG{
 
// Function to find the values
static int findAns(int a, int b, int n)
{
    // Calculate the LCM
    int lcm = (a * b) / __gcd(a, b);
 
    // Calculate the multiples of lcm
    int multiples = (n / lcm) + 1;
 
    // Find the values which satisfies
    // the given condition
    int answer = Math.max(a, b) * multiples;
 
    // Subtract the extra values
    int lastvalue = lcm * (n / lcm) + Math.max(a, b);
    if (lastvalue > n)
        answer = answer - (lastvalue - n - 1);
 
    // Return the final result
    return answer;
}
 
static int __gcd(int a, int b)
{
    return b == 0 ? a : __gcd(b, a % b);    
}
 
// Driver code
public static void main(String[] args)
{
    int a = 1, b = 13, n = 500;
    System.out.print(findAns(a, b, n) + "\n");
}
}
 
// This code is contributed by Amit Katiyar

# Python3 implementation to find the total
# count of all the numbers from 0 to n which
# satisfies the given equation for a value K
 
# Function to find the values
def findAns(a, b, n):
     
    # Calculate the LCM
    lcm = (a * b) // __gcd(a, b);
 
    # Calculate the multiples of lcm
    multiples = (n // lcm) + 1;
 
    # Find the values which satisfies
    # the given condition
    answer = max(a, b) * multiples;
 
    # Subtract the extra values
    lastvalue = lcm * (n // lcm) + max(a, b);
     
    if (lastvalue > n):
        answer = answer - (lastvalue - n - 1);
 
    # Return the final result
    return answer;
 
def __gcd(a, b):
     
    if(b == 0):
        return a;
    else:
        return __gcd(b, a % b);
         
# Driver code
if __name__ == '__main__':
     
    a = 1;
    b = 13;
    n = 500;
     
    print(findAns(a, b, n));
     
# This code is contributed by 29AjayKumar

// C# implementation to find the total
// count of all the numbers from 0 to n which
// satisfies the given equation for a value K
using System;
 
class GFG{
 
// Function to find the values
static int findAns(int a, int b, int n)
{
    // Calculate the LCM
    int lcm = (a * b) / __gcd(a, b);
 
    // Calculate the multiples of lcm
    int multiples = (n / lcm) + 1;
 
    // Find the values which satisfies
    // the given condition
    int answer = Math.Max(a, b) * multiples;
 
    // Subtract the extra values
    int lastvalue = lcm * (n / lcm) + Math.Max(a, b);
    if (lastvalue > n)
    {
        answer = answer - (lastvalue - n - 1);
    }
 
    // Return the readonly result
    return answer;
}
 
static int __gcd(int a, int b)
{
    return b == 0 ? a : __gcd(b, a % b);    
}
 
// Driver code
public static void Main(String[] args)
{
    int a = 1, b = 13, n = 500;
    Console.Write(findAns(a, b, n) + "\n");
}
}
 
// This code is contributed by sapnasingh4991

<script>
// javascript implementation to find the total
// count of all the numbers from 0 to n which
// satisfies the given equation for a value K   
// Function to find the values
    function findAns(a , b , n) {
        // Calculate the LCM
        var lcm = (a * b) / __gcd(a, b);
 
        // Calculate the multiples of lcm
        var multiples = (n / lcm) + 1;
 
        // Find the values which satisfies
        // the given condition
        var answer = Math.max(a, b) * multiples;
 
        // Subtract the extra values
        var lastvalue = lcm * (n / lcm) + Math.max(a, b);
        if (lastvalue > n)
            answer = answer - (lastvalue - n - 1);
 
        // Return the final result
        return answer;
    }
 
    function __gcd(a , b) {
        return b == 0 ? a : __gcd(b, a % b);
    }
 
    // Driver code
     
        var a = 1, b = 13, n = 500;
        document.write(findAns(a, b, n) + "\n");
 
// This code contributed by Rajput-Ji
</script>

501