最近在一道笔试题里看到了一个运算结果很大的数，会超过所有类型的最大值，题目要求结果对10^9+7取模，上网搜索这个问题的解决方法才发现这是面试中常有的问题，所以记录一下。

　　为什么要取模？是因为结果不能用任何数字类型来存储，用字符串又不方便运算，所以要进行取模操作。

　　那为什么是10^9+7?首先，10^9+7是一个足够大的质数，对于质数求模操作可能得到的结果要远大于合数，有效避免了蒙中答案的概率。另外10^9+7有一个很好的特点，相加不超过int，相乘不超过longlong。

　　那么，代码上应该怎么解决呢？

　　很简单，这利用了同余定理。

同余定理：数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。

　　在代码中，a,b相乘，对p取余，我们取a%p作为a的同余数，b%p作为b的同余数，那么(a * b)%p = (a%p * b%p)%p，根据10^9+7相乘不超过longlong的特点，我们就能避免溢出。

　　相加则类似于b=2的情况。

　　以上。

原文链接：https://luospaces.com/posts/%e5%af%b91097%e5%8f%96%e6%a8%a1