C++を使用した繰り返し単位の除算

この記事では、Nで割り切れる繰り返し単位の数を見つける方法について説明します。繰り返し単位は1の繰り返し数のみです。R（k）を繰り返し単位とします。ここで、kは1の長さです。例：R（4）=1111。したがって、R（k）がNで割り切れるkの最小数を見つける必要があります。たとえば-

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

Input : N = 31
Output : k = 15

解決策を見つけるためのアプローチ

R（k）がNで割り切れる1から始まるkの各値をチェックすることで、この問題に取り組むことができます。しかし、このソリューションでは、NがR（k）の値で割り切れるかどうかはわかりません。これにより、プログラムが複雑になりすぎて、機能しなくなる可能性があります。

このプログラムを解決するための効率的なアプローチは、です。

• Nが10と互いに素であるかどうかを確認します。
• そうでない場合、R（k）はkのどの値に対してもNで割り切れません。
• 「はい」の場合、反復単位R（1）、R（2）、R（3）...などごとに、R（i）とNの除算の余りを計算します。したがって、nがあります。残りの数。
• R（i）とR（j）の同じ剰余値を見つけます。ここで、R（i）とR（j）は2つの繰り返し単位であり、R（i）-R（j）はNで割り切れます。
• aR（i）とR（j）の差は、繰り返し単位に10の累乗を掛けたものになりますが、10とNは互いに素であるため、R（k）はNで割り切れます。

例

#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;
}

出力

Value for k : 15

結論

この記事では、R（k）のkの値を見つける方法について説明します。ここで、R（k）は、与えられたNで割り切れる繰り返し単位です。kの値を見つける楽観的な方法について説明しました。この問題を解決するためのC++コードについても説明しました。このコードは、Java、C、Pythonなどの他の言語で記述できます。この記事がお役に立てば幸いです。