• 编程竞赛有相当一部分题目的结果过于庞大，整数类型无法存储，往往只要求输出取模的结果。

• 例如(a+b)%p,若a+b的结果我们存储不了，再去取模，结果显然不对，我们为了防止溢出，可以先分别对a取模,b取模，再求和，输出的结果相同。

• 
  
  

• a mod b表示a除以b的余数。有下面的公式：
  
  

• (a + b) % p = (a%p + b%p) %p

• (a - b) % p = ((a%p - b%p) + p) %p

• (a * b) % p = (a%p)*(b%p) %p

  
  
  

举例说明：

如果我们要计算下面公式：

(a1*a2*a3*...an)%p。我们给这个公式赋值(10*20*30)%6。先按照最原始的方法运算，10*20*30=6000，然后6000%6=0

如果我们用右边的公式计算，把10*20*30进行拆分。根据公式得 （（10%6）*（20%6）*（30*6））*6 。我们可以发现10%6=4，20%6=2，30%6=0。即时我不考虑最后一个数字，前面的乘积最大才是8。也就是说，我们通过这样的方法，可以将运算过程中的大数尽量避免掉。

(adsbygoogle = window.adsbygoogle || []).push({});