##基于同余定理的快速幂 ## 再讲快速幂之前我们先来说一下同余定理这个神奇的东西哈：
同余定理：
所谓同余，字面上的意思就是两个数或者多个数的除以一个数，所得的余数相同 如果说a和b同时除以c，所得的余数均为r，那么可以写成a = mc + r ，b = nc + r(m和n为任意整数)，那么我们就可以用数学公式写成 a ≡ b (mod c)，即 a 和 b 同余。比如 9 和 2 除以 7 的余数均为2，那么我们可以写成 9 ≡ 2 (mod 7)。网上还有一种定义，即如果两个数 a 和 b 之差能被 c 整除，那么我们就说 a 和 b 对模数 c 同余（关于 c 同余）。比如，9 - 2除以 7 正好除尽，我们就说 9 和 2 对于模数 7 同余。它的另一层含义就是说，a = mc + r ，b = nc + r，( a - b ) = ( m - n )c对c能除尽，那么 a 和 b 同余。反之，令a = mc + r1 ，b = nc + r2 若c | a - b ,则c | c ( m - n ) + r1 - r2 ，则 c | r1 - r2，但| r1 - r2 | = 0，故r1 = r2,即 a ≡ b ( mod c)。 推论： a ≡ b (mod c)的充要条件是a = c t +b（t为整数，可能改成a - b = ct 好看一点）。定理1： 同余关系具有自反性、对称性、传递性，即
1） a ≡ a ( mod m) ;
2）若 a ≡ b (mod m), 则b ≡ a (mod m);
3）若a ≡ b (mod m) 且 b ≡ c (mod m)，则a ≡ c ( mod m) .
定理2：若 a ≡ b ( mod m) , c ≡ d (mod m),则 对于两个的同模同余式也能够进行加减乘运算。
1）a + c ≡ b + d (mod m);
2）a - c ≡ b - d (mod m);
3）ac ≡ bd (mod m).
第一第二个推论还挺好理解的，现在来证一下第三个推论： 设 a = wm + p ; b = xm + p ; c = ym + q ; d = zm +q ; ac = ( wy )m^2+( wq +yp)m +pq bd= ( xz ) m^2 +(xq + zp)m +pq 所以 ac ≡ bd( mod m ) 对于乘法还有下面的推论： 推论 ： 若 a ≡ b ( mod m ),n 为自然数，则 an ≡ bn ( mod m )。 有的题要叫你“输出答案mod xxxxx的结果”，这是为了避免高精度运算，因为这里的结论告诉我们在运算过程中边算边mod和算完后再mod的结果一样。
定理3： 若 ca ≡ cb ( mod m) , ( c , m ) = d, 且 a , b 为整数，则 a ≡ b ( mod m/d).
推论：若 ca ≡ cb (mod m) , ( c , m ) = 1 , 且 a , b 为整数，则 a ≡ b ( mod m ).
定理4 ：若 a ≡ b ( mod m ), a ≡ b ( mod n ),则 a ≡ b ( mod [m,n] ).
推论：若 a ≡ b ( mod mi ), i = 1,2,…,n，则 a ≡ b ( mod [m1,m2,…,mn] ).
下面我们进入各位期待的快速幂： 首先我们先了解两个公式（蒙哥马利幂模运算公式，由上面的同余定理推导出）： 1）a * b % n =（a % n ) * ( b % n ) % n 2）（a + b）% n =（a % n + b % n ) % n
一般这种题通常会让我们求 a ^ b % c ,即 a 的 b 次幂对 c 取模 ， 我们假设 a = 5 , b = 6 , c = 3 则 a 的 b 次方对 c 取模的值为5 ^ 6 % 3 ,转化为（5 ^ 2）^ 3 % 3 ，转化为（5 ^ 2）（（5 ^ 2）^2） % 3，即（（5 ^ 2）%3）（（5 ^ 2）^2 % 3）% 3 依据同余定理可得下列公式： 如 a ^ 5，可转化为（（a ^ 2）^2） a % c
以下是代码实现：
#include<iostream> using namespace std; long long remn(long long a,long long b,long long c) { long long ans = 1; a %= c; //先让a % = c是为了防止 a 很大，c很小的情况，毕竟a ≡a % c(mod c),这样做不会使(a*a)超限 while(b > 0){ if(b & 1){ //（b&1）位运算判断奇偶，b&1=1是奇数，按位与运算 ans = (ans * a) % c; //是奇数，可与之前是奇数是所求得的结果相乘求余，此时ans保存的是(之前ans乘上(a的平方次幂对c取模) )再对c取模的值 } b >>= 1; //为运算，右移一位等于除以2，最后必然得到一个奇数1，可由上方if语句求得结果 a = (a * a) % c; //若是偶数，可相乘求余，此时a保存的是之前a的平方次幂对c取模 } cout<<ans<<endl; } int main() { long long x,y,z; while(cin>>x>>y>>z){ remn(x,y,z); } return 0; }我建议读者多测试几组数据，并用编译器调试一下，看看每一步，每个变量的值是如何变化的，这样有助于理解，我就是通过调试理解的，嘻嘻，错误的地方还望各位大佬指正，谢谢
