【C++】Nで割り切れるレピュニット（繰り返し単位）の最小桁数を効率的に求める方法

はじめに

本記事では、指定された整数Nで割り切れる「レピュニット（繰り返し単位）」の桁数kを求める問題について解説します。レピュニットとは、数字の1のみが繰り返される数のことで、R(k)は1がk個並んだ数を表します。例えば、R(4) = 1111 となります。ここでの課題は、R(k)がNで割り切れるような最小のkを求めることです。

入力 : N = 13
出力 : k = 6
説明 : R(6)、つまり 111111 は 13 で割り切れます。

入力 : N = 31
出力 : k = 15

解法へのアプローチ

この問題に対する最も素朴なアプローチは、k = 1から順に各値をチェックし、R(k)がNで割り切れるかどうかを確認することです。しかし、この方法ではNがどのR(k)によっても割り切れない場合の判定が困難で、プログラムが複雑になりすぎたり、正しく動作しなかったりする可能性があります。

より効率的なアプローチは以下の通りです。

• まず、Nが10と互いに素（coprime）であるかどうかを確認します。
• 互いに素でない場合、どのkに対してもR(k)はNで割り切れません。
• 互いに素である場合、R(1)、R(2)、R(3)…と各レピュニットについて、R(i)をNで割った余りを計算します。これにより複数の余りが得られます。
• R(i)とR(j)で同じ余りの値が現れた場合、その差 R(i) − R(j) はNで割り切れることになります。
• R(i)とR(j)の差は、あるレピュニットに10のべき乗を掛けた形になります。10とNは互いに素なので、そのレピュニットR(k)はNで割り切れることが保証されます。

C++による実装例

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

int main() {
   int N = 31;
   int k = 1;
   // Nが10と互いに素かどうかを確認
   if (N % 2 == 0 || N % 5 == 0){
      k = 0;
   } else {
      int r = 1;
      int power = 1;
      // 余りが0になる（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

まとめ

本記事では、与えられた整数Nで割り切れるレピュニットR(k)の最小桁数kを求める方法について解説しました。「Nが10と互いに素であるか」を判定し、剰余計算を活用することで効率的に答えを導けることを説明しました。また、この問題を解くためのC++のコードも紹介しました。ロジックは同じなので、Java、C、Pythonなど他の言語でも容易に実装できます。本記事が皆様の学習のお役に立てば幸いです。