• 同余定理：

                      同余定理是数论中的重要概念。给定一个正整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。

同余符号

 两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对模m同余或a同余于b模m。记作a≡b(mod m) 【定义】 设m是大于1的正整数，a、b是整数，如果m|(a-b)，则称a与b关于模m同余，记作a≡b(mod m)。显然有如下事实：

• 若a≡0(mod m)，则m|a;
• a≡b(mod m)等价于a与b分别用m去除，余数相同。

同余性质

• 反身性：a≡a (mod m)
• 对称性： 若a≡b(mod m)，则b≡a(mod m)
• 传递性： 若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)
• 同余式相加：若a≡b(mod m)，b≡c(mod m)，则a ± c≡b ± d(mod m)
• 同余式相乘：若a≡b(mod m)，b≡c(mod m)，则ac≡bd(mod m)
• 线性运算：如果a≡b(mod m)，c≡d(mod m)，那么a ± c≡b ± d(mod m)，且a * c≡b * d(mod m)
• 除法：若ac ≡ bc (mod m) c≠0 则 a≡ b (mod m/gcd(c,m)) 其中gcd(c,m)表示c,m的最大公约数。特殊地 ,gcd(c,m)=1 则a ≡ b (mod m)
• 幂运算：如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)
• 若a ≡ b (mod m)，n|m,则 a ≡ b (mod n)
• 若a ≡ b (mod mi) (i=1,2…n) 则 a ≡ b (mod [m1,m2,…mn]) 其中[m1,m2,…mn]表示m1,m2,…mn的最小公倍

6.应用：

    (1)高精度对单精度取模              一个高精度数对一个数取余，可以把高精度数看成各位数的权值与个位数乘积的和。如1234 = ((1 * 10 + 2) * 10 + 3) * 10 + 4，对这个数进行取余运算就是上面基本加和乘的应用。 #include #include using namespace std; int main(){ string a; int b; cin >> a >> b; int len = a.length(); int ans = 0; for(int i = 0; i < len; i++){ ans = (ans * 10 + a[i] - '0') % b; } cout << ans << endl; return 0; }        (2)快速幂取模              将幂拆解为多个底数的平方次的积，如果指数为偶数，把指数除以2，并让底数的平方次取余，如果指数为奇数，就把多出来的底数记录下来，再执行偶数次的操作。 #include using namespace std; int PowerMod(int a, int b, int c){ int ans = 1; a = a % c; while(b > 0){ if(b&1){ ans *= (a % c); } b >>= 1; a = (a * a) % c; } ans %= c; return ans; } int main() { int a, b, c; cin >> a >> b >> c; cout << PowerMod(a, b, c) << endl; return 0; }