欧几里得算法用来快速求解两个数的最大公约数.
整除性
\(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 $
来源: http://www.bubuko.com/infodetail-2685994.html