原来联赛是考数论的...
好像很多甚至是全部没有给证明，因为大部分我找到的能看懂的证明都觉得证的不大对，有的是证了充分没有证必要，有的是太过冗余不适合整理。
一些定义和结论
剩余类：记模 (m) 为 (r)（(rin [0,m))）的自然数组成的集合为 (k_r)，则 (k_r) 为模 (m) 的一个剩余类，任意 (amod m=r)，称 (a) 为 (k_r) 的一个代表元。
完系：在每个 (k_r) 中任取一个代表元为模 (m) 的一个完系。
缩系/简化剩余系：对于每一个与 (m) 互质的 (r)，在 (k_r) 中任取一个代表元为模 (m) 的一个缩系。若 (xperp m)，则将 (m) 的一个缩系中每个数都乘 (x) 后，仍然为 (m) 的一个缩系。
裴蜀定理：(ax+by=c,xin mathbb{Z}^*,yin mathbb{Z}^*) 有整数解的充要条件是 (gcd (a,b)|c)
费马小定理：若 (gcd(a,m)=1)，则 (a^{m-1}equiv 1pmod m)
欧拉定理：若 (gcd(a,m)=1)，则 (a^{varphi(m)}equiv 1pmod m)
扩展欧拉定理：(a^{b}equiv a^{b mod varphi(m)+varphi(m)}pmod m)
Lucas 定理：
欧几里得算法（辗转相除法）：
Stein算法：
当 (a,b) 均为偶数时：(gcd(a,b)=2gcd(a/2,b/2))；
当 (a) 为偶数，(b) 为奇数时：(gcd(a,b)=gcd(a/2,b))；
当 (a) 为奇数，(b) 为偶数时：(gcd(a,b)=gcd(a-b,b))．（(a>b)）
扩展欧几里得算法（exgcd）
求解下面这个不定方程:
利用裴蜀定理判断有无解，若有解必有 (gcd(a,b)|c)．
先求解 (ax+by=gcd(a,b))
把后面的 (gcd(a,b)) 辗转相除一下再写成类似的形式（这里的 (x',y') 是对应 (gcd(b,amod b)) 的 (x,y)，和上面的 (x,y) 没有关系）：
因为要求解 (x,y)，所以假设我们已经求解了 (x',y')，则要按 (a,b) 把两个方程分开。
递归求解得到 (x',y') 后，对比系数可得 (x=y',y=(x'-leftlfloor frac{a}{b} ight floor y'))。
这样递归就能求出 (ax+by=gcd(a,b)) 一组特解了，最后当 (b=0) 的时候递归终止，此时 (ax+by=gcd(a,b)) 的解是 (x=1,y=0)．
void exgcd(int a, int b, int &x, int &y) {
if(!b) { x = 1, y = 0; return ; }
exgcd(b, a % b, x, y);
int nx = y, ny = x - (a / b) * y;
x = nx, y = ny;
}
令 (d=gcd(a,b))．
求出 (ax+by=d) 的一组特解 (ax_0+by_0=d)，则有 (afrac{x_0c}{d}+bfrac{y_0c}{d}=c)，记作 (ax_1+by_1=c)．
其通解为 (a(x_1+kfrac{b}{gcd(a,b)})+b(y_1-kfrac{a}{gcd(a,b)}))．
充分性显然，这个必要性先不证了因为我不会。
扩展中国剩余定理
合并两个一元线性同余方程：
有 (a_1+k_1m_1=a_2+k_2m_2)，整理得 (k_1m_1-k_2m_2=a_2-a_1)，用裴蜀定理判断有无解，否则 exgcd 求出一组解 ((p,q))，则原来两个方程可以合并成 (xequiv a_1+m_1ppmod {mathrm{lcm}(m_1,m_2)})，这样子合并为什么是最优的，就先不证了因为我不会。
为了防止爆精度，exgcd 求解出的使用最小非负整数解。