メモの日々

■ [math] 巨大自然数Aが自然数Bの倍数かどうかを調べる

long型では表現できない大きな数AがBの倍数かどうかを調べるにはどうするか。

倍数かどうかを知るにはAをBで割った余りが0かどうかを調べればよい。Aが大きな数でもその余りはBより大きくならないので、余りさえ計算できればうまくいく。

例えば、Aを「11111111111111111111111111111111111111111111111111」のように1が連続した整数とする。このような数は1から始めて「10倍して1を加える」という操作を繰り返すことで生成できるので、剰余演算の等価性から得られる

(10a + 1) % b = (10a % b + 1 % b) % b
              = (((10 % b)(a % b)) % b + 1 % b) % b

という変換を繰り返すことで余りを求めることができる（「a % b」はaをbで割った余りを表すものとする）。

1が連続する整数のことをレピュニット数と言うようだが、120桁のレピュニット数は5964848081の倍数らしい。それを次のコードで確認できる。

#include <iostream>

int main()
{
  const long b = 5964848081L;
  long rem = 1;
  for (int n = 2; n <= 120; ++n) {
    rem = ((10 * rem) % b + 1) % b;
  }
  std::cout << rem << std::endl;
}

0