罠の多い問題。

問題 10093 An Easy Problem!

数字 R が与えられ、それを (N-1) で割り切れる最小の基数 N (つまりN進数の基底) を求めなさい。というのが問題の内容。

例えば、R = 2727 に対して、Rは9で割り切れるので、N = 10 がその答え。

10進数の場合、9で割り切れるかどうかの判定は極めて容易。数字の各桁の和を取り、それが9で割り切れるかどうかを調べるだけで必要十分条件になるわけだ。

例えば、2+7+2+7=18 は 9で割り切れるので、Rも 9で割り切れる。2725では各桁の数字の和は9の倍数ではないので、2725 も絶対に9の倍数ではないのだ。証明は簡単なので省略する。

さて、この事実はN進数にも成り立つ。N進数において、各桁の数字の和が N-1 で割り切れるならば、その数字も N-1で割り切れる。それを利用して、

各桁の数字が
  ’0′ ~ ‘9’ なら 0~9、
  ’A’ ~ ‘Z’ なら 10~35、
  ’a’ ~ ‘z’ なら 36~61
に置き換えて、素直に足していく。その合計を sum とする。

また、N進数において、各桁の表現できる最大数は N-1 (つまり2進数では1、10進数では 9 、16進数では15(便宜上Fと表現するが)のこと)なので、基数は最大数字の一つ上以上でないといけない。2727の例では基数は8からということだ。なお、1の基数 (1進数、死の世界)は認められていないので、最小基数は2となる。

その(最小基数-1) で 合計のsumを割って行き、割り切れたらそこで終了。1つずつ増やして62になっても割り切れないならば ”such number is impossible!” と出力。

例えば、 2727に対し、sum = 18。8では割り切れないが、つぎの9でOK。したがって、N = 10となる。

さて、これで問題が解けたのかと思ったら大間違い。苦戦苦闘の末判ったのが、

 1.入力の数字に符号+か ー が含まれている。
 2.入力数字の桁数は異常に長い。1000桁以上の数字が存在 している。2000桁の配列(入力バッファとして使っている)を取ったら、やっとACもらった。2000桁であっても、sumは整数で十分。各桁の大きさは61までなので、最大でも12万強。

最後にテストデータと結果。

Sample Input
0
1010101101
  +265
    -5464
z
Zz

Sample Output
2   ←最小基数は2だから
2   ←0と1からなる数字列は1で割り切れるから、すべては2進数
14
20  ←マイナス符号は関係ないので、読み飛ばしてOK。
62
such number is impossible!

Comments are closed.

Post Navigation