1.数论

1.整除关系
a|b 表示b mod a=0
若a|b且a|c，则a|(bx+cy)
最大公约数GCD(a,b) 辗转相除
最小公倍数LCM(a,b)
GCD(a,b)LCM(a,b)=ab
2.同余关系
a≡b(mod m) //a-b能被某个自然数m整除
等价于 a mod m=b mod m
3.同余关系的性质
若a≡b(mod m)
a+c ≡b+c(mod m)
ac ≡bc(mod m)
如果a≡b(mod m)，x≡y(mod m)，则a+x≡b+y(mod m)
如果a≡b(mod m)，x≡y(mod m)，则ax≡by(mod m)
若a mod p=x且a mod q=x,p和q互质，则a mod(pq)=x
如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m)
如果c和m不互质：
g=gcd(c,m)//最大公约数
a≡b(mod m/g)//c与m/g互质
a≡b（mod m/y)(c与m不一定互质)
4.辗转相除
求gcd(a,b)
Gcd(a,b)=gcd(a mod b, b)
Gcd(a,b) = gcd( a – b, b)
求ax+by=c的整数解
其中c|gcd(a,b)
我们不妨设c=gcd(a,b)（若不等最后答案乘以一个c/gcd(a,b)即可）
5.辗转相除（裴蜀定理）
若b=0那么x=1,y=0;
否则
考虑 ax+by=gcd(a,b）与 bx’+(a mod b) y’=gcd(a,b)解的关系
bx’+(a-b*(a/b))y’=gcd(a,b) 这里的除法为整除
ay’+b(x’-(a/b)y’)=gcd(a,b)
所以 x=y’ y=x’-(a/b)y’
就这样迭代下去就可以得出ax+by=gcd(a,b) 的一组解 要变换其他的解只需要
x+kb,y-ka即可
6.逆元
求0<=x<b的x满足 ax=1 (mod b)
gcd(a,b)=1
这样的x我们称为在mod b意义下的a的逆元
7.费马小定理 ap-1%p=1
8.剩下不会，下一个

2.比赛

今天比赛再创历史“新高”
直接爆0了（鬼知道我第一题怎么RE的
1.chicken 最小生成树（但炸了
2.dusk 实在是太“easy”了，简单到不想打了
（为什么连一个“NO”都没有，样例实在是太高明了
3.dog
打了暴力，但挂了
不是我说，它是怎么做到，插队往后插的啊
而且还是一个一个往后插的？
4.贪心，但是我不会；

LAST

不完美没有爆0的s组是不完美的！！！！
（非常的高兴，zmx也爆0了！！！！！！！！
（J组括号匹配实在是水了，不知道小语同学是怎么过的