前言
数学我的一生之敌
(本篇 blog 基本没有证明,你杠我就是我对,我们不生产知识,我们只是知识的搬运工)
(不写证明才不是因为笔者 \(\LaTeX\) 用得不熟呢)
裴蜀定理
结论
对于任意正整数 \(\text{a, b}\),存在整数 \(\text{s, t}\) 使得 \(sa + tb = \gcd(a,b)\)
证明
运用辗转相除法 oi-wiki
推论
- \(\gcd(ad, bd) = t \times \gcd(a, b)\)
- 若 \(\gcd(a, b) = 1\),则 \(\gcd(a, bc) = gcd(a, c)\)
- 设方程 \(ax + by = c\) 的特解 \(x_0 = x, y_0 = y\), 那么\(x = x_0 + t \dfrac{b}{\gcd(a, b)}\) , $ y = y_0 - t \dfrac{a}{\gcd(a, b)}$
扩展欧几里得
int exgcd(int a, int b, int &x, int &y){
if(!b){
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
x = y;
y = t - a / b * y;
return d;
}
//得到的结果是 ax + by = gcd(a, b)
质因数分解
只因数分解?(雾
int cnt;
int fac[maxn];
void getfac(int n){
for(int i = 2; i * i <= n; i ++){
if(!(n % i)){
fac[++ cnt] = i;
while(!(n % i))n /= i;
}
}
if(n > 1)fac[++ cnt] = n;
}
标签:因数分解,数论,gcd,笔记,int,text,ax,自留
From: https://www.cnblogs.com/Nefelibata/p/17057530.html