取余数有%，即
<blockquote>
10%3
</blockquote>
可以得到1
但是当数比较大时(比如2999999)，计算机可能就无法计算
然而，根据数论的结论，我们可以简化一下。

根据<code>a*b mod c = ( (a mod c) * (b mod c) ) mod c</code>
可以得出 <code>an mod b = (a mod b)n mod b</code>
所以，有 <code>an mod b = (a mod b)n mod b = (a mod b)n/22 mod b = (an/2 mod b)2 mod b = (an/2 mod b)2 mod b</code>
如果用<code>exp_mod(a,n,b)</code>表示an mod b那么就是<code>exp_mod(a,n,b) = exp_mod(a,n/2,b)*exp_mod(a,n/2,b) mod b</code>
那么我们可以不断二分幂，从而减小运算
有几种特殊情况需要考虑
<ol>
<li>n=0，也即a^n=1，此时模为1%b</li>
<li>n=1，这时二分已经到了终点，可以直接用a%b得到答案</li>
<li>n为奇数，此时n/2会被舍去小数部分，会少乘一个a mod b，可以在补上a mod b</li>
</ol>
代码如下：
<pre style="background-color:#fff">typedef long long LL;
LL exp_mod(LL a,LL n,LL b){
 LL t;
 if(n==0) return 1%b;
 if(n==1) return a%b;
 t=exp_mod(a,n/2,b);
 t=t*t%b;
 if((n&amp;1)==1) t=t*a%b;
 return t;
}
</pre>

快速幂取模