算法拾遗[2]——数论算法

发表于 | 分类于

夏令营复习算法, 感到自己对之前学过的算法略有生疏, 写篇流水账, 权当复习.

  • 素数筛法
  • 快速幂取模
  • 扩展欧几里得/求逆元

素数筛法

一种用已知的小素数 \(p\) 来筛掉更大的合数, 最终留下素数的算法. 实践复杂度 \(O(n\log\log n)\).

实现代码 1: 打标记

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int maxn = 1e6 + 5;

bool notprime[maxn];
void init()
{
    memset(notprime, false, sizeof(notprime));
    notprime[0] = notprime[1] = true;
    for(int i = 2; i < maxn; i++)
    {
        if(!notprime[i])
        {
            if(i > maxn / i) continue; // 防止i * i 溢出
            for(int j = i * i; j < maxn; j += i)
                notprime[j] = true;
        }
    }
}

实现代码 2: 直接存素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int maxn = 1e6 + 5;

int prime[maxn];
void getPrime()
{
    memset(prime, 0, sizeof(prime));
    for(int i = 2; i < maxn; i++)
    {
        if(!prime[i]) prime[++prime[0]] = i;
        for(int j = 1; j <= prime[0] && prime[j] <= maxn / i; j++)
        {
            prime[prime[j] * i] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}

事实上也可以先打标记, 再 for 一遍把素数拿出来.

百练 3177: 判决素数个数

总时间限制: 1000ms 内存限制: 65536kB

描述

输入两个整数X和Y，输出两者之间的素数个数（包括X和Y）。

输入

两个整数X和Y（1 <= X,Y <= 105）。

输出

输出一个整数，表示X，Y之间的素数个数（包括X和Y）。

样例输入

1 100

样例输出

25

大致思路

有个坑点… 题目没有保证 \(x\leqslant y\).. 所以需要 swap 一下.

AC代码

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
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5;

bool notprime[maxn];
void init()
{
    memset(notprime, false, sizeof(notprime));
    notprime[0] = notprime[1] = true;
    for(int i = 2; i < maxn; i++)
    {
        if(!notprime[i])
        {
            if(i > maxn / i) continue;
            for(int j = i * i; j < maxn; j += i)
                notprime[j] = true;
        }
    }
}

int main()
{
    int x, y;
    init();
    while(cin >> x >> y)
    {
        int ans = 0;
        if(x > y) swap(x, y);
        for(int i = x; i <= y; i++)
            if(!notprime[i]) ans++;
        cout << ans << endl;
    }

    return 0;
}

扩展欧几里得算法

求解 \(ax+by=d\) 中的 \(x, y\), 其中 \(\gcd(a, b)~|~d\) 才有解.

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 返回d = gcd(a, b); 和对应于等式ax + by = d 中的x, y
long long extend_gcd(long long a, long long b, long long &x, long long &y)
{
    if (a == 0 && b == 0)
        return -1; // 无最大公约数
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extend_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

快速幂取模

在 \(O(\log n)\) 时间内求 \(a^n~\%m\) 的值.

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
long long pow_mod(int a, int b)
{
    long long ret = 1;
    while(b)
    {
        if(b & 1)
            ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

求逆元

求 \(x\), s.t. \(ax=1~({\rm mod}~m)\).

实现代码 1: 利用扩展欧几里得

1
2
3
4
5
6
7
8
9
10
// ax = 1 (mod n)
long long mod_reverse(long long a, long long n)
{
    long long x, y;
    long long d = extend_gcd(a, n, x, y);
    if (d == 1)
        return (x % n + n) % n;
    else
        return -1;
}

实现代码 2: 利用费马小定理

由于模数 \(m\) 一般为素数, 当 \((a,m)=1\) 时, 由费马小定理有: \[a^{m-1}=1~({\rm mod}~m)\Rightarrow a^{-1}=a^{m-2}.\] 

1
2
3
4
long long inv(int a)
{
    return pow_mod(a, mod - 2);
}