Divisibilité des unités répétitives (en utilisant C++)

Dans cet article, nous discuterons de la recherche du nombre d'unités répétitives divisible par N. Une unité répétitive est simplement le nombre de répétitions de 1, soit R(k) l'unité répétitive, où k est la longueur de 1. Par exemple, R(4) = 1111. Nous devons donc trouver le nombre minimum de k pour lequel R(k) est divisible par N comme -

Input : N = 13
Output : k = 6
Explanation : R(6) i.e 111111 is divisible by 13.

Input : N = 31
Output : k = 15

Façon de trouver la solution

Vous pouvez résoudre ce problème en vérifiant chaque valeur de k à partir de 1 où R (k) Est-ce divisible par N ? Mais en utilisant cette solution, nous ne pourrons pas déterminer si N est divisible par une valeur de R(k). Cela rendra le programme trop complexe et pourrait même ne pas fonctionner.

Un moyen efficace de résoudre ce programme est de :

• Vérifier si N est premier avec 10.
• Sinon, alors R(k) n'est divisible par N pour aucune valeur de k.
• Si oui, alors pour chaque unité répétitive R(1), R(2), R(3)...etc., calculez le reste de la division R(i) par N, il y a donc n restes.
• Trouvez le même reste de R(i) et R(j), où R(i) et R(j) sont deux unités répétitives telles que R(i) - R(j) est divisible par N.
• aR La différence entre (i) et R(j) multipliera l'unité répétitive par une puissance de 10, mais 10 et N sont relativement premiers, donc R(k) sera divisible par N.

Exemple

#include <bits/stdc++.h>
using namespace std;

int main() {
   int N = 31;
   int k = 1;
   // checking if N is coprime with 10.
   if (N % 2 == 0 || N % 5 == 0){
      k = 0;
   } else {
      int r = 1;
      int power = 1;
      // check until the remainder is divisible by N.
      while (r % N != 0) {
         k++;
         power = power * 10 % N;
         r = (r + power) % N;
      }
   }
   cout << "Value for k : "<< k;
   return 0;
}

Sortie

Value for k : 15

Conclusion

Dans cet article, nous discutons de la recherche de la valeur k de R(k), où R(k) est une unité répétitive divisible par un N donné. Nous avons discuté d’une approche optimiste pour trouver la valeur de k. Nous avons également discuté du code C++ pour résoudre ce problème. Vous pouvez écrire ce code dans n'importe quel autre langage comme Java, C, Python, etc. Nous espérons que cet article vous a été utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!