主要代码



long mod(long a,long b,long m) { if(!b) return 1; //边界处理 if(b==1) return a%m; //边界处理 long ans=mod(a,b/2,m); //进入下一层 ans=ans*ans%m; //返回值ans代表a if(b&1) ans=ans*a%m; //奇数情况处理 return ans; //返回ans代表a modm }
续上




按照上述的方法继续分下去… 最终肯定会得到 21 mod 3 这种情况！这样 就好办了！这便是递归的边界，到此我们就 可以返回2 mod 3的值了！ 另一个问题，再分时有两种情况！ 2100=(250)2 , 100是偶数 299=(249)2 *2 , 99是奇数 第二种情况需要在第一种情况上乘上一次基 数。
b/2 b
调用



上述函数是有三个参数，且有返回值！ 它的功能是计算ab mod m的值！ 如何在主函数里调用呢？ 例如我们要计算2100mod3的结果！我们可 以首先定义一个变量ans，在主函数读入工 作完成后，我们可以写 ans=mod(2,100,3); ans 里的数值便是2100mod3的结果了。
高次幂取模
(快速幂取模) (张鹏)
基本概念及思想

对形如ab mod m 的运算（b一般较大） 但a,b,m都在long型范围内 算法的主要思想是分治，分而治之。将大的 问题分成若干个相似的较小的问题！ 具体实现是用递归的方法！

举例



2100 mod 3 像这种运算如果先算出2100 的值，然后再模 上3，相信比较困难！ 我们可以将100变小点 2100=(250)2 =((225)2)2=((((21)2)2)…)2 若我们已经得出250 mod 3的值，我们便很 简单地得出2100 mod 3的值。
递推法





用递推法首先要将b转换为二进制数， (b)10=(b)2。 举例: (45)10=(101101)2 545 mod 3 =2 二进制数由0和1组成，它们分别代表着偶数 和奇数。 递推时在0和1处的处理是有差别的。
参考代码



二进制转换： long s=0; while(b>0) { t[++s] = b%2; b/=2;long ans=1; for(i=1;i<=s;i++) if(t[i]) ans=ans*ans*a%m; else ans=ans*ans%m;
End

Thank you