欧几里得算法

  • 又称辗转相除法

  • 求a, b的最大公约数，相当于求b, a mod b的最大公约数

  • gcd缩写表示最大公约数

1
2
3
int gcd(int a, int b){
    return b ? gcd(b, a % b) : b;
}

算术基本定理

  • 又称因式分解定理
  • 所有的整数都可以唯一分解成若干个质因子乘积的形式
  • N = P1^ d1 P2 ^ d2 … * Pk ^ dk;//Pi是质数，di > 0;

求矩形的数量以及求正方形的数量

假设有一个n m的矩阵，则矩形共有n m个，正方形共有枚举右下角[i,j]，min(i, j)个

埃氏筛

1
2
3
4
5
6
7
8
9
10
void get_prime(int x){
    if(x == 1) return;
    for(int i = 2; i <= x; i++){
        if(!st[i]){
            prime[cnt++] = i;
            for(int j = i + i; j <= n; j += i) st[j] = true;
        }
        
    }
}

线性筛

1
2
3
4
5
6
7
for(int i = 2; i <= n; i++){
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] <= n / i; j++){
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
}