レピュニットの計算(自作問題)

問題

レピュニットとは全ての桁が1であるような自然数をいう。(例えば、1,11,111,1111など)。

10と互いに素である自然数nの倍数には、必ずレピュニットが存在することが知られている。具体的に言うと、3の倍数には111があり、7の倍数には111111がある。

10^8以下の自然数nが入力されるとき、その倍数である最小のレピュニットを求めよ。

入力

10と互いに素である自然数nが入力される。

出力

倍数である最小のレピュニットの桁数を出力せよ。

入出力例

入力 -> 出力

3    -> 3 (=111)

7    -> 6 (=111111)

11  -> 2

99  -> 18

27  -> 27

解説

R(k) はk番目のレピュニットを示すものとする。R(1)=1,R(2)=11,といった具合である。

次のような漸化式が成立する。

R(k+1)=10R(k)+1

両辺のnによる剰余は次のようになる。

R(k+1)%n=(10%n*R(k)%n+1%n)%n

この式を用いれば、答えを出すことが出来る。

解答例コード(C)

#include<stdio.h>

int main(void){

  unsigned int m,n,i,k,s;

  scanf("%u",&m);

  for(n=0;;n++){

    for(i=0;i<=n;i++){

      if(i==0){

s=1%m;

k=1;

      }else{

k*=10;

k%=m;

s+=k;

s%=m;

      }

    }

    if(s==0){

      printf("%d\n",n+1);

      break;

    }

  }

  return 0;

}