Comprueba si un número S puede hacerse divisible por D sumando repetidamente el resto a S

Dados dos enteros S y D , la tarea es verificar si el entero S puede hacerse divisible por D o no sumando repetidamente S módulo D a S. Si S es divisible por D , imprima “Sí” . De lo contrario, escriba “No” .

Ejemplos:

Entrada: S = 3, D = 6
Salida: Sí
Explicación: 
Digamos que el valor en el i ^-ésimo intervalo mod D es V(i), es decir, V(i) = (V(i – 1) + V(i – 1) % D) % D entonces, 
V(0) = S % D = 3
V(1) = (V(0) + V(0) % D) % D = (3 + (3%6)) % 6 = 0
Entonces, 6 es divisible por 6. Por lo tanto, imprime «Sí».

Entrada: S = 1, D = 5
Salida: No

Enfoque: el problema dado se puede resolver utilizando el principio de Pigeon Hole . Siga los pasos a continuación para resolver el problema:

• De acuerdo con el principio, si hay más de D números que se toman módulo con D , entonces al menos un valor en el rango ([0, D – 1]) ocurrirá dos veces.
• Itere por (D + 1) veces y almacene el valor de V(i) en un HashMap , y si hay una repetición, salga del ciclo.
• Hay un caso límite cuando el valor restante es 0 , salga del ciclo en ese caso y este es un caso de divisibilidad, pero nuestra lógica lo trata como un ciclo.

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 check if S is divisible
// by D while changing S to (S + S%D)
string isDivisibleByDivisor(int S, int D)
{
    // V(0) = S % D
    S %= D;
 
    // Stores the encountered values
    unordered_set<int> hashMap;
    hashMap.insert(S);
 
    for (int i = 0; i <= D; i++) {
 
        // V(i) = (V(i-1) + V(i-1)%D) % D
        S += (S % D);
        S %= D;
 
        // Check if the value has
        // already been encountered
        if (hashMap.find(S)
            != hashMap.end()) {
 
            // Edge Case
            if (S == 0) {
                return "Yes";
            }
            return "No";
        }
 
        // Otherwise, insert it into
        // the hashmap
        else
            hashMap.insert(S);
    }
    return "Yes";
}
 
// Driver Code
int main()
{
    int S = 3, D = 6;
    cout << isDivisibleByDivisor(S, D);
 
    return 0;
}

// Java program for the above approach
import java.lang.*;
import java.util.*;
 
class GFG{
     
// Function to check if S is divisible
// by D while changing S to (S + S%D)
static String isDivisibleByDivisor(int S, int D)
{
     
    // V(0) = S % D
    S %= D;
 
    // Stores the encountered values
    Set<Integer> hashMap = new HashSet<>();
    hashMap.add(S);
 
    for(int i = 0; i <= D; i++)
    {
         
        // V(i) = (V(i-1) + V(i-1)%D) % D
        S += (S % D);
        S %= D;
 
        // Check if the value has
        // already been encountered
        if (hashMap.contains(S))
        {
             
            // Edge Case
            if (S == 0)
            {
                return "Yes";
            }
            return "No";
        }
 
        // Otherwise, insert it into
        // the hashmap
        else
            hashMap.add(S);
    }
    return "Yes";
}
 
// Driver code
public static void main(String[] args)
{
    int S = 3, D = 6;
     
    System.out.println(isDivisibleByDivisor(S, D));
}
}
 
// This code is contributed by offbeat

# Python 3 program for the above approach
 
# Function to check if S is divisible
# by D while changing S to (S + S%D)
def isDivisibleByDivisor(S, D):
    # V(0) = S % D
    S %= D
 
    # Stores the encountered values
    hashMap = set()
    hashMap.add(S)
 
    for i in range(D+1):
       
        # V(i) = (V(i-1) + V(i-1)%D) % D
        S += (S % D)
        S %= D
 
        # Check if the value has
        # already been encountered
        if (S in hashMap):
           
            # Edge Case
            if (S == 0):
                return "Yes"
            return "No"
 
        # Otherwise, insert it into
        # the hashmap
        else:
            hashMap.add(S)
    return "Yes"
 
# Driver Code
if __name__ == '__main__':
    S = 3
    D = 6
    print(isDivisibleByDivisor(S, D))
 
    # This code is contributed by bgangwar59.

// C# program for the above approach
using System;
using System.Linq;
using System.Collections.Generic;
 
class GFG {
     
// Function to check if S is divisible
// by D while changing S to (S + S%D)
static string isDivisibleByDivisor(int S, int D)
{
    // V(0) = S % D
    S %= D;
   
    // Stores the encountered values
    List<int> hashMap = new List<int>();;
    hashMap.Add(S);
   
    for (int i = 0; i <= D; i++) {
   
        // V(i) = (V(i-1) + V(i-1)%D) % D
        S += (S % D);
        S %= D;
   
        // Check if the value has
        // already been encountered
        if (hashMap.Contains(S)) {
   
            // Edge Case
            if (S == 0) {
                return "Yes";
            }
            return "No";
        }
   
        // Otherwise, insert it into
        // the hashmap
        else
            hashMap.Add(S);
    }
    return "Yes";
}
 
    // Driver Code
    static void Main()
    {
        int S = 3, D = 6;
        Console.Write( isDivisibleByDivisor(S, D));
    }
}
 
// This code is contributed by sanjoy_62.

<script>
      // JavaScript program for the above approach
      // Function to check if S is divisible
      // by D while changing S to (S + S%D)
      function isDivisibleByDivisor(S, D)
      {
       
        // V(0) = S % D
        S %= D;
 
        // Stores the encountered values
        var hashMap = [];
        hashMap.push(S);
 
        for (var i = 0; i <= D; i++)
        {
         
          // V(i) = (V(i-1) + V(i-1)%D) % D
          S += S % D;
          S %= D;
 
          // Check if the value has
          // already been encountered
          if (hashMap.includes(S)) {
            // Edge Case
            if (S == 0) {
              return "Yes";
            }
            return "No";
          }
 
          // Otherwise, insert it into
          // the hashmap
          else hashMap.push(S);
        }
        return "Yes";
      }
 
      // Driver Code
      var S = 3,
        D = 6;
      document.write(isDivisibleByDivisor(S, D));
       
      // This code is contributed by rdtank.
    </script>

Yes

Tiempo Complejidad: O(D)
Espacio Auxiliar: O(D)