c++ - c++中大量数字的模算术mod

Question

在我短暂的体育编程生涯中，我遇到了很多次计算数字模型，例如

26164615615665561165154564545......%(10000007)

我做了一些研究，但只能找到表格中数字模型的计算

(a^b)%c

任何人都可以解释如何像第一个例子那样计算数字的模数。

Answer 1

作为标准库的一部分，C++ 没有任何长整数算术工具。如果要使用长整数进行计算，则需要依赖外部库。

似乎有两个不错的选择

• 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

I have found the solution(maybe)

So,here goes explaination.If we want to calculate mod of very big numbers that cannot be stored as any data type than we have to take number as a string.Than we will do something like this

 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;
 }

Why does it work ?Take a paper and pen and start doing division of string with the number first(taking 100) for ease.

  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:This is my first answer.Sorry i wrote answer to my own question but i thought it would be good for future readers.