問題
レピュニットとは全ての桁が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;
}
0 件のコメント:
コメントを投稿