算法之美

选自 微信 的 算法之美.

• 预计每天进行更新

数论及其算法

素数的判定

• 基础的素数判定

  bool isprime(int a){
  	if(a < 2) return true;
  	for(int i = 2; i * i <= a; i++){
  			if(a % i == 0) return false;
  	}
  	return true;
  }

• 埃式筛

  如果这个数字是素数的话，那将这个数字的倍数 都不可能是素数

  int prime[N],cnt = 0;
  bool Num[N];
  void erathic(int n){
  		for(int i = 2; i <= n; i++){
  			if(!num[i]){prime[cnt++] = i;}
  			for(int j = i * i; j <= n; j += i){num[j] = true;}
  		}
  }

• 欧拉筛

  每个 合数（非素数） 只被自己的 最小质因子 筛掉

int prime[N],cnt = 0;
bool num[N];

int euler(int n){
    menset(num,false,sizeof(num))
	num[0] = num[1] = true;
	for(int i = 2; i <= n; i++){
		if(!num[i]){ prime[cnt++] = i; }
		for(int j = 0; j < cnt && prime[j] * i <= n; j ++){
			num[prime[j] * i] = true;
			if(i % prime[j] == 0) break; // 不再继续，因为 i * prime[j + 1] 被设置的话，就不满足 每个合数 被 最小质因子 筛掉 这个条件
		}
	}
}

欧几里得算法

最大公约数的重要性质：

a, b 的最大公约数，相当于 a * x 和 b * y，随意整数x, y,使得 a * x 和 b * y 的差值最小

• 基本GCD

  算法 核心：gcd(a, b) = gcd(b, a % b), gcd(n, 0) = n

  正确性核心：gcd(a, b) = gcd(a, a - b), a % b = a - (a / b)*b

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

• 扩展 欧几里得算法

  基本问题：a * x + b * y = gcd(a,b) 求 x, y

  • a mod b →(a - (a / b) * b)

  int gcd(int a, int b, int &x, int &y){
  	if(b == 0){
  		x = 1; y = 0;
  		return a;
  	}
  	int t = gcd(b, a % b, x,y);
  	int t1 = x;
  	x = y;
  	y = t - (a / b) % y;
  }

  • 贝祖定理(裴蜀定理)

    基本形式：a * x + b * y = gcd(a, b)，x, y 为随机数

    • 如果 a * x + b * y = 1 意味着 a，b互质。
    • a * x + b * y = k * gcd(a, b)