ACM数论

个人认为这部分的数论中的基础，刚刚又查了查蓝桥杯不考数论，所以这篇博客的数论知识都是一些基础知识。准备蓝桥杯还是好好学学动态规划和图论吧!

质数

质数概念: 从2开始，只包含1和本身的约数，又称素数。

性质: 若有n整除d，则n整除d/n $$ d | n \rightarrow \frac{d}{n} | n $$

1-试除法判断质数模板

1
2
3
4
5
6
7


bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2; i <= n / i; i++){
        if(n % i == 0) return false;
    }
    return true;
}

2-分解质因数(求一个数的所有质因数)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


void divide(int n){
    for(int i = 2; i <= n / i; i++){
        if(n % i == 0){
            int s = 0;
            while(n % i == 0)n /= i,s++;
            // i 是底数，s是指数(有多少个i)
            cout << i << " " << s << endl;
        }
    }
    if(n > 1) cout << n << " " << 1 << endl;
}

3-筛素数(判断1-n之间有多少个素数)

普通方法:枚举1-(n-1)来看看是否能筛掉n这个数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


void get_primes(int n){
  for(int i = 2; i <= n ;i++){
      if(st[i] == false){
          ans++;
      }
      for(int j = i + i; j <= n; j+=i){
          st[j] = true;
      }
  }
}

埃氏方法:枚举1-(n-1)中的质数来看看是否能筛掉n这个数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


void get_primes(int n){
  for(int i = 2; i <= n ;i++){
      if(st[i] == false){
          ans++;
          for(int j = i + i; j <= n; j+=i){
              st[j] = true;
          }
      }
  }
}

线性方法:使用n的最小质因数来筛掉n

1
2
3
4
5
6
7
8
9


void get_primes(int n){
    for(int i = 2; i <= n ;i++){
        if(!st[i]) primes[ans++] = i;
        for(int j = 0; primes[j] <= n / i; j++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

4-试除法求约数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

5-约数相关公式

如果约数: $ N = p_{1}^{a1} * p_{2}^{a2} ... p_{k}^{ak} $

约数个数: $ (a_{1} + 1) * (a_{2} + 2) * ... * (a_{k} + 1)$

约数之和: $ (p_{1}^0 +p_{1}^1 +... +p_{1}^{a1}) * ... * (p_{k}^0 +p_{k}^1 +... +p_{k}^{ak}) $

6-欧几里得算法(辗转相除法求最小公因数)

1
2
3


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

7-求欧拉函数

定义: 1-N中于N互质的个数被称为欧拉函数，记为$ \phi(N)$

如果约数: $ N = p_{1}^{a1} * p_{2}^{a2} ... p_{k}^{ak} $

求法: $ \phi(N) = N * (1 - \frac{1}{p_1}) * (1 - \frac{1}{p_2}) * ... * (1 - \frac{1}{p_k}) $

8-筛法求欧拉函数

通过线性筛求很多欧拉函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

9-快速幂

求$m^k \mod p$ 时间复杂度logk

1
2
3
4
5
6
7
8
9


LL f(LL a,LL b,LL p){
    LL res = 1;
    while(b){
        if(b & 1) res = (res * a) % p;
        a = (a * a) % p;
        b>>=1;
    }
    return res % p;
}

10-求组合数

朴素求组合数,适用范围0-1000以内左右的组合数

1
2
3
4
5
6
7
8


const int N = 1010;
int C[N][N];
for(int i = 0; i < N; i++){
  for(int j = 0; j <= i; j++){
    if(!j) C[i][j] = 1;
    else C[i][j] = C[i-1][j] + C[i-1][j-1];
  }
}

ACM数论

相关文章：