\(\texttt{godmoo}\text{ }\texttt{の}\text{ }\texttt{数论学习笔记 之}\text{ }\boxed{因数与倍数}\)
定义
-
因数/约数，倍数：若 \(d \mid n\)，则 \(d\) 是 \(n\) 的因数，\(n\) 是 \(d\) 的倍数。
-
公因数/公约数，公倍数：公共的因数/约数、倍数。
-
最大公因(约)数：\(GreatestCommonDivisor(gcd)\)，最大的公因数，规定 \(gcd(0,a)=a\)。
-
最小公倍数：\(LeatestCommonMultiple(lcm)\)，最小的公倍数。
\(eg.\text{ }gcd(24,18)=6,lcm(24,18)=72\)
性质
- 唯一分解定理：任意大于 \(1\) 的整数都可以写成有限个质数乘积的形式，即：
\(n=\prod_{i=1}^m p_i^{c_i}\) - \(gcd\) 和 \(lcm\) 的最值表示法：若有 \(x=\prod_{i=1}^m p_i^{a_i}\)，\(y=\prod_{i=1}^m p_i^{b_i}\)，则有：
正确性：由定义推出。
- \(gcd\) 与 \(lcm\) 的性质：\(x \times y=gcd \times lcm\)
正确性：由 \(gcd\) 和 \(lcm\) 的最值表示法推出。
\(\bold{gcd}\) 求法
- 分解质因数：分解后用 \(gcd\) 的最值表示法，\(O(\sqrt{n})\)
- 欧几里得算法：又名辗转相除法，\(gcd(a,b)=gcd(b,a\text{ }mod\text{ }b)\)
证明：
记 \(g=gcd(a,b)\)
\(\large\text{Part1.}\) 证明是公因数
首先 \(g\) 是 \(a\),\(b\) 的因数；
我们知道，\(a\text{ }mod\text{ }b=a-\lfloor\frac{a}{b}\rfloor b\) ；
那么 \(g\) 也是这个式子的因数；
所以 \(g\) 是 \(b\) 和 \(a\text{ }mod \text{ }b\) 的公因数。
\(\large\text{Part2.}\) 证明是最大公因数
假设存在更大的公因数 \(k\)；
则 \(k \mid b\) 且 \(k \mid a-\lfloor\frac{a}{b}\rfloor b\)；
于是 \(k \mid b\) 且 \(k \mid a\)；
此时，\(k\) 是 \(a\) 和 \(b\) 的公因数；
又 \(k \gt g\)，与 \(g=gcd(a,b)\) 矛盾；
所以 \(g=gcd(b,a\text{ }mod\text{ }b)\)。
ll gcd(ll x,ll y){
if(!y) return x;
return gcd(y,x%y);
}
也可以写成：
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
- 更相减损术：\(gcd(a,b)=gcd(b,a-b)\)
证明：与辗转相除法的类似，不证。
- \(\bm{Stein}\) 算法：
针对大数据时，取模运算的性能会很低，使得辗转相除法的效率不佳；但更相减损术的效率又不高，每次只能减一此。于是，\(Stein\) 算法横空出世，它避免了取模运算，但实测下来，它在大数据下的表现略胜一筹。
思想：\(Stein\) 算法基于更相减损术，由于计算机是以 \(2\) 进制存储的，所以位运算的效率极高，所以考虑用位移运算优化更相减损术。
流程：
\(Case\text{ }1:\) 当 \(a,b\) 一奇一偶时，
偶数除以 \(2\)，显然不影响结果；
\(Case\text{ }2:\) 当 \(a,b\) 都是偶数时，
答案为 \(2\text{ }gcd(\frac{a}{2},\frac{b}{2})\)；
\(Case\text{ }3:\) 当 \(a,b\) 都是奇数时，
无法优化，直接做更相减损术；
\(【性质】:\text{ }\)\(Case\text{ }3\) 后必为 \(Case\text{ }1\)，效率得到保证。
ll stein(ll x,ll y){
if(x<y) x^=y,y^=x,x^=y; // swap的黑科技
if(!y) return x;
if(!(x&1)&&!(y&1)) return stein(x>>1,y>>1)<<1;
if(!(x&1)&&(y&1)) return stein(x>>1,y);
if((x&1)&&!(y&1)) return stein(x,y>>1);
return stein(y,x-y);
}