int main() { int a, n, m; a = 3; n = 13; m = 7; a = a % m; int r = 1; while (n >0) { if (n & 1) { r = (r * a)%m; } a = (a * a)%m; n=n >> 1; } printf("%d", r); return 0; }，想问下快速幂的r = (r * a)%m;a = (a * a)%m;这两条公式取模为啥不会影响运算，没搞明白原理
原理是同余定理 若a≡b (mod m)，则： b≡a (mod m) a+c≡b+c (mod m) a-c≡b-c (mod m) a*c≡b*c (mod m) a/c≡b/c (mod m/gcd(c, m)) 因此，若a≡b (mod m)，根据同余定理，有a*a≡b*b (mod m) 用代数关系表示是：若a % m = b, 则(a * a) % m = (b * b) % m 如果你对其中的数学原理感兴趣，可以学习初等数论。
