数论！！！

请先阅读[前言]后再阅读本博客

前言

以下的看不看得懂无所谓，看就对了

辗转相除法，GCD

辗转相除法用来求两个数的最大公约数，又称欧几里得算法，其原理:

$$GCD(x,y)=GCD(x,y-x)$$

证明如下:

• 设$z|x$,$z|Y$,则$z|(y-x)$。
• 设$z$不是$x$的因子，则z不是x,y-x的公因子。
• 设z|x，z不是y的因子，则z不是x，y-x的公因子。

代码部分：

int GCD(int x,int y){
	return y==0 ? x:GCD(y,x%y);
}

gsx整理了一下GDC版的二进制代码

inline intGCD(int x,int y){
	int i,j;
	if(x==0) return y;
	if(y==0) return x;
	for(int i=0;0==(x&1);++i)x>>1;//去掉所有的2
	for(int j=0;0==(y&1);++j)y>>=1;//去掉所有的2
	if(j<i) i=j;
	while(1){
		if(x<y)x^=y,y^=x,x^=y;//若x>y，交换x、y
		if(0==(x-=y)) return y<<i;
		while(0==(x&1))x>>=1//去掉所有的2
	}
}

求两个数的最小公倍数可以使用“逐步倍增”法，还可以直接使用以下定理求解:

定理:a、b两个数的最大公约数乘它们的最小公倍数就等于a和b本身的乘积。

扩展欧几里得算法

• 核心：通过递归实现 ax + by = gcd(a,b) 的整数解
• 递归终止条件：当 b = 0 时返回 (a, 1, 0)
• 参数更新：通过余数迭代传递解参数 x 和 y
• 应用：求最大公约数及线性方程的特解（需标注：递归回溯过程需注意参数传递方向）

斐波那契数列

• 递推公式：F(n) = F(n-1) + F(n-2)，初始值 F(1)=1, F(2)=1
• 通项公式：$$F(n) = \frac{\sqrt{5}}{5}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n] $$
• 性质：
  • 前 $n$ 项和 $S(n) = F(n+2) - 1$
  • 前n项和$s[n]=a1+a2+...+an=2a[n]+a[n-1]-1=a[n+2]-1;$
  • 奇数项和:$a1+a3+...+a[2n-1]=a[2*n];$
  • 偶数项和:$a2+a4+a[2n]=a[2n+1]-1;$
  • 平方和:$a1^2+a2^2+...a_n^2=a[n]*a[n-1];$
  • 中项:$3a[i]=a[i-2]+a[i+2];$

素数判定与筛法

• 朴素判定法：
  • 时间复杂度：$O(\sqrt{N})$
  • 优化：仅需遍历到 $\sqrt{N}$，跳过非素数因数

埃拉托斯特尼筛法

• 普通筛：标记所有素数的倍数（存在重复标记）
• 线性筛（优化版）：
• 每个合数仅被最小质因数筛除
• 复杂度：O(N log log N)
• 关键步骤：通过维护素数列表避免重复筛除（需标注：线性筛的倍数遍历逻辑需仔细理解）
• 关键条件：i % primes[j] == 0时终止循环

核心要点：

• 线性筛通过最小质因数保证每个数仅被筛一次
• 时间复杂度优化至O(N)的实现条件
• 普通筛法与线性筛的复杂度对比（O(N log log N））
• 循环终止条件的数学判定逻辑
• 重复标记问题的代码优化方案

循环控制：

for i from 2 to N:  
    if is_prime[i]: 添加至质数表  
    for j in 质数表前K项:  
        if i * primes[j] > N: break  
        标记is_prime[i*primes[j]] = false  
        if i % primes[j] == 0: break  # 核心优化点 

重复标记规避：通过提前终止内层循环，避免大数被多次标记

标注

最小质因数筛选的数学证明：

当i % primes[j] == 0时，后续质数与i的乘积必然包含更小的质因数，因此需终止循环以避免重复计算（需结合数论中的因式分解定理理解）

未完待续