说明

最近遇到的一些笔试问题，关于大数的情况还是很多，因此在这里做一个小的说明，关于大数取余的过程，典型的运算就是幂！

大数取模

一般而言，取模的数字是1000000007（一般也会写作1e9+7，一共十位数），对于这个数的一些问题，我只能做一个小的总结吧，有很多的数学解释我在后面就直接放链接了。

首先我觉得他是一个质数，而且足够大，因此在计算的时候不会很多麻烦，取余也比较方便；
其次int32的最大值是2147483647，所以对于int32位来说1000000007足够大；
最后int64的最大值是2^63-1，对于1000000007来说它的平方不会在int64中溢出所以在大数相乘的时候，因为(a∗b) % c=((a%c) ∗ (b%c)) % c，所以相乘时两边都对1000000007取模，再保存在int64里面不会溢出。

这句话在做题的时候看上去只需要取模就可以了，但是在实际计算中还是有一些小坑，因此还是小小总结一下。

关于快速幂

快速幂运算其实就是二分法。假设要求x^n，如果n = 2^k，那么原题可以很轻松的表示为：x^n = ((x^2)^2)^2…。这样只要做k次平方运算就能解决，时间复杂度就从O(n)下降到log(n)。
示例代码如下（中间还做了大数取余的过程）：

long long mod(long long a, long long b) {
	long long ans = 1;
	long long c = 1000000007;
	while(b > 0) {
		if(b & 1) ans = ans * a % c; 
		a = a * a % c;
		b >>= 1;                     //位运算：b /= 2; 
	}	
	return ans;
}

两个易错点

求最大值时先取模

取mod的时候，如果题目要求你算最大值，并且说由于答案可能很大，输出结果请对1e9+7取，那你千万不能在max函数更新最大值时就取模，这样很可能会出错！

比如：题目过程中有四个数据

1	2e9+7，1e9+6，1e9+5，1e9+4

然后算法中你用max求最大值时，如果先模上1e9+7，那你会得到1e9，1e9+6，1e9+5，1e9+4，并且max函数算出的最大值是1e9+6，可是这四个数的最大值应该是2e9 + 7才对。

正确做法：在求max的时候不要先取mod，而是都以long long型数据比大小，最后得到最大值是2e9 + 7，再对它取mod，得到结果是1e9 + 7。

直到return才取模

如果让你算1+2+…+n的值（由于答案可能很大，输出结果请对1e9+7取）
n的取值范围是1 ~ 10^10000。

那显然如果在中间过程中不先取mod，必然会爆数据范围，因为不管是int还是long long甚至是double(最大10^308)都无法存下这个数据。

//	...
long long res = 0;
for(int i = 1; i <= n ; i++) 
    res = res + i; // n巨大，res无法存下这个数据
return res % (1e9 + 7);
//	...

正确的做法应该是计算的过程中取模：

//	...
long long res = 0;
for(int i = 1; i <= n ; i++) 
    res = (res + i) % (1000000007); // 计算的过程中取模
return res;
//	...

总结

如果回想上面，做幂运算的时候就是这样的过程，也是在运算的过程中进行取余的。总结起来就是在做题的开始就需要想好，到底是先取余还是计算以后取余。