欧几里得算法用来快速求解两个数的最大公约数。
整除性
\(a|b\)表示\(a\)整除\(b\)，即\(b\)是\(a\)的倍数。
定理1：设\(a,b,c\)为整数，若\(a|b, a|c\)，则\(a|(b+c)\)成立
证明： 设\(b = sa, c = ta（s,t为整数）\)，则\(b+c = sa + ta = a(s+t)\)，故\(a | (b+c)\)
最大公约数
\(gcd(a, b)\)表示\(a,b\)的最大公约数。
最暴力的求解最大公约数的方法是枚举\(a,b\)的所有公约数，并取相同的最大的公约数。但很明显太浪费时间了。
欧几里得是怎么做的？
要求解\(gcd(a,b)\)，通过不断求解$ gcd(b, a \% b) $直到$ a \% b = 0 $时，取\(b\)作为答案。
代码实现：
int gcd(int a, int b){ return b==0?a:gcd(b,a%b); }
注意为什么不用判断\(a\)和\(b\)的大小？因为当\(a < b\)时$ a \% b $ == \(a\)
$ S(n,k)= \sum\limits_{i=0}^kC_{n/p}^{i/p}*C_{n \%p}^{i \%p}\ mod\ p $
原文：https://www.cnblogs.com/qixingzhi/p/9312928.html