数论算法

发表于 更新于 分类于 ， 阅读次数： 本文字数： 872 阅读时长 ≈ 3 分钟

质数

试除法-判定 O(sqrt(n))

1
2
3
4
5
6
7
8
bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ ) // i * i可能会爆int，使用等价写法
        if (x % i == 0)
            return false;
    return true;
}

试除法-分解质因数 O(log n) - O(sqrt(n))

1
2
3
4
5
6
7
8
9
10
11
12
void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

朴素筛法求素数

1
2
3
4
5
6
7
8
9
10
11
12
13
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

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

线性筛法求素数

介绍参考文末引用文章

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

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

试除法求约数

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;
}

求欧拉函数

欧拉函数是求小于等于n的数中与n互质的数的数目

1
2
3
4
5
6
7
8
9
10
11
12
13
int phi(int x) // phi 是欧拉函数/fa/读音
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

筛法求欧拉函数

法一

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
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);
        }
    }
}

法二

来自博客园

需要用到如下性质

p为质数

  1. $phi(p)=p-1$ 因为质数 p 除了 1 以外的因数只有 p，故 1 至 p 的整数只有 p 与 p 不互质

  2. 如果i mod p = 0, 那么 $phi(i * p)=phi(i) * p$

  3. 若i mod p ≠0, 那么 $phi( i * p )=phi(i) * ( p-1 )$

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
#include<cstdio>
using namespace std;
const int N = 1e6+10 ;
int phi[N], prime[N];
int tot;//tot计数，表示prime[N]中有多少质数
void Euler(){
    phi[1] = 1;
    for(int i = 2; i < N; i ++){
        if(!phi[i]){
            phi[i] = i-1;
            prime[tot ++] = i;
        }
        for(int j = 0; j < tot && 1ll*i*prime[j] < N; j ++){
            if(i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j]-1);
            else{
                phi[i * prime[j] ] = phi[i] * prime[j];
                break;
            }
        }
    }
}

int main(){
    Euler();
}

​

快速幂

原理：$A^{n}=(A^{n/2})^2$

  • 如果是偶数幂，计算平方根次幂

  • 如果是奇数幂，计算$n - 1$次幂

递归实现（伪代码）

1
2
3
4
5
6
int binpow(int a,int n){
	if n==0 return 1; 
    if n是奇数 reutrn binpow(a,n-1);
       n是偶数 return binpow(a,n/2)*binpow(a,n/2);
       // 用 t 储存 binpow(a,n/2)，return t*t;
}

利用十进制转二进制的原理，可以进行非递归运算

非递归优化（C++）（位运算）

1
2
3
4
5
6
7
8
9
10
11
12
int binpow(int a,int n){
	int res = 1;
	while(n){
		/*如果n末位为1，把对应幂乘进去*/
		if (n & 1) 
			res *=a;
		/*计算位对应的幂*/
		a*=a;
 		n>>=1;
	}
	return res;
}

GCD 最大共因子

1
2
方法1 gcd(a,b)=gcd(b,a mod b) if b == 0 return
方法2 gcd(a,b)=gcd(b,a - b)

可扩展至 gcd(a,b,c,…,n)

参考

  1. AcWing
  2. 素数筛 - 知乎Pecco用户