Comprobar si N se puede obtener mediante la suma o resta repetitiva de dos números dados

Dados tres enteros positivos N , A y B, la tarea es comprobar si es posible obtener N sumando o restando A y B varias veces. 

Ejemplos:

Entrada: N = 11, A = 2, B = 5 
Salida: SI 
Explicación:  11 = 5 + 5 + 5 – 2 -2

Entrada: N = 11, A = 2, B = 4 
Salida: NO 
Explicación: No es posible obtener 11 solo de 2 y 4. 
 

Enfoque: 
siga los pasos a continuación para resolver el problema:

• La tarea es comprobar si es posible sumar o restar A y B varias veces y obtener N como resultado final.
• Por lo tanto, en términos de ecuación lineal, se puede escribir como: 
  Ax + By = N ,  
  donde x e y representan el número de veces que se suman o se restan A y B. Negativo x representa A se resta x veces y de manera similar, negativo y representa B se resta y veces
• Ahora, el objetivo es encontrar las soluciones integrales para la ecuación anterior. Aquí, es bastante válido usar el Algoritmo de Euclides Extendido que dice que las soluciones existen si y solo si N % mcd(a, b) es 0.

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

// C++ Program to check if
// a number can be obtained
// by repetitive addition
// or subtraction of two numbers
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check and return if
// it is possible to obtain N by
// repetitive addition or subtraction
// of A and B
bool isPossible(int N, int a, int b)
{
    // Calculate GCD of A and B
    int g = __gcd(a, b);
 
    // Condition to check
    // if N can be obtained
    if (N % g == 0)
        return true;
    else
        return false;
}
 
// Driver Code
int main()
{
    int N = 11, a = 2;
    int b = 5;
 
    if (isPossible(N, a, b))
        cout << "YES";
    else
        cout << "NO";
}

// Java program to check if
// a number can be obtained
// by repetitive addition
// or subtraction of two numbers
class GFG{
     
// Recursive function to return
// gcd of a and b
public static int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
     
// Function to check and return if
// it is possible to obtain N by
// repetitive addition or subtraction
// of A and B
public static boolean isPossible(int N, int a,
                                 int b)
{
     
    // Calculate GCD of A and B
    int g = gcd(a, b);
     
    // Condition to check
    // if N can be obtained
    if (N % g == 0)
        return true;
    else
        return false;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 11, a = 2;
    int b = 5;
     
    if (isPossible(N, a, b))
        System.out.print("YES");
    else
        System.out.print("NO");
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program to check if
# a number can be obtained
# by repetitive addition
# or subtraction of two numbers
 
# Recursive function to return
# gcd of a and b
def gcd(a, b):
     
    if (b == 0):
        return a
    return gcd(b, a % b)
     
# Function to check and return if
# it is possible to obtain N by
# repetitive addition or subtraction
# of A and B
def isPossible(N, a, b):
     
    # Calculate GCD of A and B
    g = gcd(a, b)
     
    # Condition to check
    # if N can be obtained
    if (N % g == 0):
        return True
    else:
        return False
         
# Driver code
N = 11
a = 2
b = 5
 
if (isPossible(N, a, b) != False):
    print("YES")
else:
    print("NO")
 
# This code is contributed by code_hunt

// C# program to check if
// a number can be obtained
// by repetitive addition
// or subtraction of two numbers
using System;
 
class GFG{
     
// Recursive function to return
// gcd of a and b
static int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
     
// Function to check and return if
// it is possible to obtain N by
// repetitive addition or subtraction
// of A and B
static bool isPossible(int N, int a,
                              int b)
{
     
    // Calculate GCD of A and B
    int g = gcd(a, b);
     
    // Condition to check
    // if N can be obtained
    if (N % g == 0)
        return true;
    else
        return false;
}
 
// Driver code
public static void Main()
{
    int N = 11, a = 2;
    int b = 5;
     
    if (isPossible(N, a, b))
        Console.Write("YES");
    else
        Console.Write("NO");
}
}
 
// This code is contributed by chitranayal

<script>
 
// Javascript program to check if
// a number can be obtained
// by repetitive addition
// or subtraction of two numbers
 
// Recursive function to return
// gcd of a and b
function gcd(a, b)
{
    if (b == 0)
        return a;
         
    return gcd(b, a % b);
}
 
// Function to check and return if
// it is possible to obtain N by
// repetitive addition or subtraction
// of A and B
function isPossible(N, a, b)
{
     
    // Calculate GCD of A and B
    var g = gcd(a, b);
     
    // Condition to check
    // if N can be obtained
    if (N % g == 0)
        return true;
    else
        return false;
}
 
// Driver code
var N = 11, a = 2;
var b = 5;
 
if (isPossible(N, a, b))
    document.write("YES");
else
    document.write("NO");  
     
// This code is contributed by Ankita saini
    
</script>

YES

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