繰り返し単位の可分性 (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

解を見つける方法

これは、k をそれぞれチェックすることで実行できます。この問題を解決するには、1 つの値から開始します。ここで、R(k) は N で割り切れます。しかし、この解決策を使用すると、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) は、R(i) - R(j) が N で割り切れる 2 つの繰り返し単位です。 .
• 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 などの他の言語で作成できます。この記事がお役に立てば幸いです。

以上が繰り返し単位の可分性 (C++ を使用)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。