c++ - C ++での巨大な数のモジュラー算術mod

Question

私の短いスポーツプログラミングのキャリアの中で、私は何度も遭遇しました

26164615615665561165154564545......%(10000007)

私はいくつかの調査を行いましたが、フォームの数値のmodの計算しか見つけることができませんでした

(a^b)%c

最初の例のような数値の mod を計算する方法を誰か説明できますか?

Answer 1

C++ には、標準ライブラリの一部として長整数演算機能がありません。long 整数で計算したい場合は、外部ライブラリに依存する必要があります。

2つの良い選択があるようです

• GMP: https://gmplib.org - C ライクなインターフェイスを恐れていない場合 (gmpxx もあります)
• NTL: http://www.shoup.net/ntl/ - 私の個人的なお気に入りで、明確で簡単なインターフェイスを提供します (例: 長整数の場合はクラス ZZ、長整数モジュロの場合は ZZ_p)。

以下は、 NTLを使用して剰余累乗を行う方法の例 ( NTL の例から取得) です。

ZZ PowerMod(const ZZ& a, const ZZ& e, const ZZ& n)
{
   if (e == 0) return ZZ(1);

   long k = NumBits(e);
   ZZ res;
   res = 1;

   for (long i = k-1; i >= 0; i--) {
      res = (res*res) % n;
      if (bit(e, i) == 1) res = (res*a) % n;
   }
   if (e < 0)
      return InvMod(res, n);
   else
      return res;
}

Answer 2

私は解決策を見つけました（多分）

したがって、ここに説明があります。どのデータ型としても格納できない非常に大きな数値の mod を計算したい場合は、数値を文字列として取得する必要があります。

 int remainder(string &s,first)
 {
   int rem=0;
   for(int i=0;i<s.length();++i)
   rem=rem*10+(s[i]-'0');//Explaining this below
   return rem;
 }

なぜそれが機能するのですか?紙とペンを用意して、最初に文字列を数字で割ります (100 を取る)。

  For example, for 1234 % 100.
  1 mod 100 = 1
  12 mod 100 =(1 * 10 + 2) mod 100 =12
  123 mod 100 =(12 * 10 + 3) mod 100 =23
  1234 mod 100 =(23 * 10 + 4) mod 100 =34

PS:これは私の最初の回答です。申し訳ありませんが、自分の質問に対する回答を書きましたが、将来の読者にとっては良いと思いました。