31 数论算法

31.1 基础数论概念

整除性与约数

Pasted image 20241123223727.png

素数与合数

Pasted image 20241123223817.png

除法定理、余数和等模

Pasted image 20241123223832.png

公约数与最大公约数

Pasted image 20241123223851.png
Pasted image 20241123223909.png
Pasted image 20241123223931.png

互质数

Pasted image 20241123224008.png
Pasted image 20241123224031.png

唯一因子分解定理

Pasted image 20241123224046.png

31.2 最大公约数

Pasted image 20241124204903.png

欧几里得算法

递归调用次数

int euclid(int a, int b){
	if(b == 0){
		return a;
	}else{
		return euclid(b, a%b);
	}
}

Pasted image 20241124204922.png
Pasted image 20241124205100.png
Pasted image 20241124205112.png

欧几里得算法的扩展形式

用于计算满足下列条件的整系数和：，其中和可能为0或负数
递归调用次数

// 法1
#include <bits/stdc++.h>  
using namespace std;

int d, x, y;  

void extendedEuclid(int a, int b){  
    if(b == 0){  
        d = a, x = 1, y = 0;  
    }else{  
        extendedEuclid(b, a%b);  
        int tempX = x;  
        x = y, y = tempX-(int)floor(a/b)*y;  
    }  
}
int main() {  
    int a, b;  
    scanf("%d%d", &a, &b);  
    extendedEuclid(a, b);  
    printf("%d = gcd(%d, %d) = %d*%d+%d*%d", d, a, b, a, x, b, y);  
    return 0;  
}

// 法2  
#include <bits/stdc++.h>  
using namespace std;  
  
  
int exgcd(int a, int b, int &x, int &y){  
    if(b == 0){  
        x = 1, y = 0;  
        return a;  
    }  
    int g = exgcd(b, a%b, y, x);  
    y -= a/b*x;  
    return g;  
}  
int main() {  
    int a, b, x, y;  
    scanf("%d%d", &a, &b);  
    int d = exgcd(a, b, x, y);  
    printf("%d = gcd(%d, %d) = %d*%d+%d*%d", d, a, b, a, x, b, y);  
    return 0;  
}