同余模是一个大家容易忽视的点，它一般不会单独作为考点出现，而是在其他类型的题目中作为一个常识的形式出现。

定义

所谓的同余，顾名思义，就是许多的数被一个数 d 去除，有相同的余数。d 数学上的称谓为模。如 a = 6, b = 1, d = 5, 则我们说 a 和 b 是模 d 同余的。因为他们都有相同的余数 1 。

数学上的记法为： 

a≡ b(mod d)

可以看出当 n < d 的时候,所有的 n 都对 d 同商，比如时钟上的小时数，都小于 12，所以小时数都是模 12 的同余.对于同余有三种说法都是等价的,分别为: 

(1) a 和 b 是模 d 同余的. 
(2) 存在某个整数 n ,使得 a = b + nd . 
(3) d 整除 a - b . 

可以通过换算得出上面三个说话都是正确而且是等价的.

定律
同余公式也有许多我们常见的定律，比如相等律，结合律，交换律，传递律….如下面的表示: 

1) a≡a(mod d) 
2) a≡b(mod d)→b≡a(mod d) 
3) (a≡b(mod d),b≡c(mod d))→a≡c(mod d)

如果a≡x(mod d),b≡m(mod d),则 

4) a+b≡x+m （mod d） 
5) a-b≡x-m(mod d) 
6) a*b≡x*m(mod d )

应用

(a+b)%c=(a%c+b%c)%c;
(a-b)%c=(a%c-b%c)%c; 
(a*b)%c=(a%c*b%c)%c;

求S(n)
题目描述：
S(n)=n^5
求S(n)除以3的余数
输入描述：
每行输入一个整数n，(0 < n < 1000000) 
处理到文件结束
输出描述：
输出S(n)%3的结果并换行
输入样例#:
1
2
输出样例#:
1
2
题目来源：
DreamJudge 1500

题目解析：通过分析我们可以发现，n虽然不大，但是n^5却超过long long的范围，所幸的是题目只要我们对答案%3，这时候我们就可以运用同余模定理。
S(n)%3=(n^5)%3=(n*n*n*n*n)%3=((n%3)*(n%3)*(n%3)*(n%3)*(n%3))%3

参考代码

#include<stdio.h>  
#include<iostream>  
using namespace std;  
  
int main() {  
    long long int n;  
    while(~scanf("%lld",&n)) {  
        long long int s=n;  
        // 同余模定理：  
        for(int i=1;i<5;i...

掌握同模余定理