首页 > 其他分享 >数论学习笔记(自留向)

数论学习笔记(自留向)

时间:2023-01-17 12:22:36浏览次数:60  
标签:因数分解 数论 gcd 笔记 int text ax 自留

前言

数学我的一生之敌

(本篇 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

相关文章