一、基本概念和性质
1、模运算的介绍
模运算即求余运算：在数学中用符号 mod 表示。模 p 运算的定义如下：
给定一个正整数 p，任意一个整数 n，一定存在等式：n=kp+r（k、r 是整数，且 0<=r < p），称 k 为
n 除以 p 的商，r 为 n 除以 p 的余数，记着：r=n mod p。
针对模 p 运算，可以数环来理解：一个圆环有 p 米，并标刻度：0,1,…,p-1：
◆k=n/p：表示一个人在这个环上沿顺时针跑的长总长度 n，k 表
示跑的整圈数；
◆r=a mod p，r 表示这个人最后停留在 r 点上；
2、模算术公式
(a+b) mod p = (a mod p + b mod p) mod p
(a*b) mod p = ((a mod p) * (b mod p)) mod p
(a-b) mod p = ((a mod p)-(b mod p) + p) mod p
在 C++中有求余运算符号’%’，也是求余数功能，但和 mod 有区别，mod 的结果一定是非负数，
而%则不一定，但参与运算的数都是正整数的情况下是等价的。例如：
a%p=(a mod p + p)mod p
%的运算规则是：a%b = a-a/b*b
3、同余的概念
如果 a 和 b 除以 p 的余数相同，则说 a 和 b 关于模 p 同余，记作：
a≡b(mod p) ÍÎ a mod p = b mod p
定理：a≡b(mod n) 的充要条件 a-b=n*y（即 a-b 是 n 的倍数）
这个定理得证明很简单:b mod n == (b+y*n) mod n == a mod n
利用这个定理，请完成：P1833
4、剩余系的概念
所谓“剩余系”，就是指对于某一个特定的正整数 n，一个整数集中的数模 n 所得的余数域。
例如 n=10，则整数集：{5,20,14,17,15}的剩余系为{0,4,5,7}
如果一个剩余系中包含了这个正整数所有可能的余数（一般地，对于任意正整数 n，有 n 个余数：
0,1,2,…,n-1），那么就被称为是模 n 的一个完全剩余系。
在剩余系中，每个元素代表的是一个同余等价类：比如 n=5，则元素 3 代表了
{3,8,13,18,…,3+k*5}
二、扩展欧几里德算法
例 1、解的个数（P1135）
已知整数 x,y 满足如下条件：ax+by+c=0; 其中:x1<=x<=x2 ; y1<=y<=y2。求(x,y)的解的个
数。
【输入格式】
第一行：n,有 n 个任务。n<=10,以下有 n 行，每行为：a,b,c,x1,x2,y1,y2.
其中 a,b,c,x1,x2,y1,y2 都是绝对值不超过 10^8 的整数。
【输出格式】
有 n 行，第 i 行是第 i 个任务的结果。
【讲解】
1、解答本题需要讨论很多情况，见下面的算法主框架：
void solve()
{
if(x1>x2 || y1>y2){printf(”0 ”); return;} //特殊情况
if(a==0 && b==0) 解的情况;
if(a==0 && b!=0) 解的情况;
if(a!=0 && b==0) 解的情况;
if(a!=0 && b!=0)
{
解的情况;//这是本题的重点和难点(见 2)
}
}
2、ax+by+c=0 的整数解（直线上的整数点）
把方程变形为：ax+by=c，数论方法求解方程的整数解的方法——扩展殴几里德算法：
一个重要结论：ax+by=c 只有在 c 是 gcd(a,b)的倍数的情况下才有整数解
证明：设 g=gcd(a,b)，则 ax+by 一定是 g 的倍数，所以 c 一定是 g 的倍数
有了上述结论，要求 ax+by=c 的整数解，先求 ax+by=g 的整数解。
1）、扩展欧几里德算法
欧几里德辗转相除法的基本原理：gcd(a,b)=gcd(b,a%b)
所以： ax + by = g //g=gcd(a,b)
==> bx’ + (a%b)y’ = g
==> bx’ + (a-a/b*b)y’ = g
==> ay’ + b(x’-a/b*y’) = g
==> x=y’、y=x’-a/b*y’ //迭代式
根据迭代式，可以在欧几里德辗转相除法求 a,b 的最大公约数时，同时计算 ax+by=g 的一
个整数解！
int gcd(int a,int b)
{
if(b==0) returen a;
int g=gcd(b,a%b);
return g;
}
int exgcd(int a,int b,int &x,int &y)
{
if(b==0) { x=1; y=0; return a;} // g*1=g
int xx,yy;
int g=exgcd(b,a%b,xx,yy);
x=yy;
y=xx-(a/b)*yy;
return g;
} 2）、扩展欧几里德算法调用
调用：int g=exgcd(a,b,x,y)后，得到 ax + by = g 的一个解(x,y)。
要得到 ax+by=c 的解：
I)、如果 c%g!=0，则方程 ax+by=c 无解
I)、如果 c%g==0，则方程 ax+by=c 的一个解为：x0=c/g*x , y0=c/g*y
从而可得到 ax+by=c 的通解形式： x=x0+k*b/g , y=y0-k*a/g; (其中 k 为任意整数)
由此，可知道，在本题的主算法中：
if(a!=0 && b!=0)
{
讨论：x1<= x0+k*b/g <=x2，y1<= y0-k*a/g <=y2 中 k 的解集
}
三、线性同余方程：
例 2、同余方程（P1778）
求关于 x 的同余方程：ax≡1(mod b)，输入的 a 和 b 保证有解！（2<=a,b<2*109
）
3 10 7
【讲解】
我们把：ax≡c(mod b)称为线性同余方程，
根据同余定理可得：ax≡c(mod b) Î ax-c=by Î ax-by=c
void solve()
{
int a,b,c,g,x,y;
scanf(“%d%d”,&a,&b); //ax≡1(mod b)Î ax+by=1
b=-b,c=1;
int g=exgcd(a,b,x,y);
if(c%g==0)
{
int x0=c/g*x, y0=c/g*y;
// 计算最小的正整数解，即在 k 取多少的时候， x0+k*b/g 是最小的正整数；
}
return 0;
}
四、逆元
我们知道，在实数下：ax=1，则 x=1/a，称 x 为 a 的倒数，那么在整数中，如果 ax≡1(mod b)，
中的 x 称为 a 模 b 的逆元（相当于倒数）。记着 x=a-1。 那么如何求解逆元呢？——上题就是逆元？
只有当 a、b 互素的情况下，a 存在逆元！
int mod_inverse(int a,int b)
{
int x,y;
exgcd(a,b,x,y);
return (x%b+b)%n; //最小正整数解
}
例题、圆周上的追击（P1844）
在一个周长为 n+1 公里的圆周上每隔 1 公里有个驿站，顺时针方向编号依次为 0,1,2,…,n。现
在甲乙两人分别从圆周上某驿站出发，按顺时针方向前进。甲从编号为 i 的驿站出发，每天走 A 公里，
然后休息；乙从编号为 j 的驿站出发，每天行走 B 公里，然后休息。问最少多少天，他们才能休息在同
一个驿?
【输入】
一行四个整数输入：n,i,j,A,B
【输出】
一个整数，表示最少多少天他们能在同一驿站休息，如果永远也不会有这种情况发生，输出-1。
【样例】
5 0 2 3 4 2
【数据范围】
0