c - 2つの非常に大きな数と非常に大きな数の掛け算のモジュラスを見つける

Question

プログラミングの演習では、他の計算の一部として 1000000007 を使用して、2 の 500000 乗 (入力の最大数) のような非常に大きな数のモジュラスを見つける必要があります。

何度も調べる必要があるかもしれないので、1 つの方法は、5,00,000 の配列を作成することです。しかし、それは大量のメモリをブロックしているので、これを行うためのより良い方法があることを知りたいですか?

Answer 1

次のような単純なものはどうですか?:

#include <stdio.h>

unsigned long PowMod(unsigned long p)
{
  unsigned long prod;

  if (p == 0)
    return 1;
  if (p == 1)
    return 2;

  prod = PowMod(p / 2);
  prod = (unsigned long long)prod * prod % 1000000007ULL;
  if (p % 2 != 0)
  {
    prod = prod * 2 % 1000000007ULL;
  }

  return prod;
}

int main(void)
{
  printf("%lu\n", PowMod(3));
  printf("%lu\n", PowMod(4));
  printf("%lu\n", PowMod(30));
  printf("%lu\n", PowMod(31));
  printf("%lu\n", PowMod(32));
  printf("%lu\n", PowMod(33));
  return 0;
}

出力 ( ideone ):

8
16
73741817
147483634
294967268
589934536