算法基础-数学知识-欧拉函数、快速幂、扩展欧几里德、中国剩余定理

欧拉函数

互质就是两个数的最大公因数只有1，体现到代码里面就是a和b互质，则b mod a = 1 mod a (目前我不是很理解，但是可以这样理解：a和b的最大公因数是1，即1作为除数和b作为除数时，对于被除数a来说余数是一样的，即1/a的余数和b/a是一样的，即b mod a = 1 mod a)
欧拉函数的作用是求1-n与n互质的个数

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

void get_eura(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; ++ i)
    {
        if (x % i == 0)
        {
            //res = res * (1 - 1/i);或者res = res * (i - 1) / i;都不行，前者是浮点数1 后者会溢出
            res = res / i * (i - 1);
            while (x % i == 0)
            {
                x /= i;
            }
        }
    }
    if (x > 1) res = res / x * (x - 1);
    cout << res << endl;
}
void solve()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        get_eura(x);
    }
}
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T --) solve();
    return 0;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50

AcWing 874. 筛法求欧拉函数

线性筛 + 欧拉函数（有一点推公式）

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 1e6 + 10;
int primes[N], st[N], eulers[N];
int cnt;
void get_eulers(int x)
{
    eulers[1] = 1;  
    for (int i = 2; i <= x; ++ i)//只是在线性筛的过程中顺便求了一下每个数的欧拉函数
    {
        if (!st[i])//1-n的质数
        {
            primes[cnt++] = i;
            eulers[i] = i - 1;
        }
        for (int j = 0; primes[j] <= x / i; ++ j)//1-n的合数//任何合数都含有质因数，4 = 1 * 2 * 1 * 2；
        {
            st[primes[j] * i] = 1;
            if (i % primes[j] == 0)
            {
                eulers[i * primes[j]] = eulers[i] * primes[j];
                break;//其实也相当于一个else
            }
            //eulers[i * primes[j]] = eulers[i] * primes[j] / primes[j] * (primes[j] - 1);
            eulers[i * primes[j]] = eulers[i] * (primes[j] - 1);
        }
    }
}
void solve()
{
    int n;
    cin >> n;
    get_eulers(n);
    long long res = 0; 
    for (int i = 1; i <= n; ++ i) res += eulers[i];
    cout << res;
}
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T --) solve();
    return 0;
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

快速幂

1 2 4 8成指数倍增长 log的时间复杂度

AcWing 875. 快速幂

long long qmi(int a, int b, int p)
{
    long long res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % p;
        }
        a = a * (long long)a % p;
        b >>= 1;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

AcWing 876. 快速幂求逆元

欧拉函数 =>费马定理 =>快速幂实现费马定理计算结果

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

long long qmi(int a, int b, int p)
{
    long long res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = (long long)a * a % p;
        b >>= 1;
    }
    return res;
}
void solve()
{
    int n;
    cin >> n;
    while (n --)
    {
        int a, p;
        cin >> a >> p;
        if (a % p == 0) cout << "impossible" << endl;
        else cout << qmi(a, p - 2, p) << endl;//a需要与m互质，否则a不存在乘法逆元
    }
}
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T --) solve();
    return 0;
}
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
37
38
39
40
41
42
43
44

扩展欧几里德（裴蜀定理）

AcWing 877. 扩展欧几里得算法

ll gcd(ll x,ll y)
{
    if(y==0)    {return x;}
    return gcd(y,x%y);
}
1
2
3
4
5

这是一个求最大公约数（Greatest Common Divisor，简称GCD）的函数实现。

该函数的参数为两个整数x和y，返回值为它们的最大公约数。在函数中，我们使用递归的方式来求解最大公约数。

具体地，我们先判断y是否为0。如果y等于0，那么x就是最大公约数，直接返回x即可。否则，我们将x对y取模，得到余数r，然后递归调用gcd(y, r)来求解y和r的最大公约数。由于r一定小于y，因此每次递归调用时，y都会不断减小，直到y等于0，此时x就是最大公约数。

例如，当x=12，y=18时，我们可以按照如下步骤来求解它们的最大公约数：

gcd(12, 18)
-> gcd(18, 12)
-> gcd(12, 6)
-> gcd(6, 0)
最终结果为6，即12和18的最大公约数为6。
这个函数的实现基于欧几里得算法，也叫辗转相除法。这个算法的基本思想是，两个整数的最大公约数等于其中较小的数和两数之差的最大公约数。通过不断地将较大的数对较小的数取模，我们可以将两个数的大小逐渐缩小，直到其中一个数为0，此时另一个数就是最大公约数。这个算法的时间复杂度为O(logn)，其中n为两个整数的较大值
理解递归的本质：

裴蜀定理和线性同余方程的证明：

#include 
#include 

using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    //d就是最大公约数，本题其实用不到
    int d = exgcd(b, a % b, y, x);//本题的精髓
    /*
    只是为了方便更改x和y的值，如果用
    d = exgcd(b, a % b, x, y);
    最后就解得 新x = y 新y = x - a / b * y
    那么代码就得这么写
    int t = y;
    y = x - a / b * y;
    x = t;
    显然比只要写一句 新y -= a / b * x; 麻烦
    */
    y -= a / b * x;
    return d;
}
void solve()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a, b, x, y;
        cin >> a >> b;
        exgcd(a, b, x, y);
        cout << x << " " << y << endl;
    }
}
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T --) solve();
    return 0;
}
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
37
38
39
40
41
42
43
44
45
46
47
48

AcWing 878. 线性同余方程

线性同余方程用扩展欧几里德定理求解
本题推导过程在上面
为什么要% m

#include 
#include 

using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    else//其实不用else，上面满足直接return了，上面不满足也会走到下面 
    {
        int d = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
}
void solve()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a, b, m, x, y;
        cin >> a >> b >> m;
        int d = exgcd(a, -m, x, y);
        if (b % d != 0) cout << "impossible" << endl;
        else cout << (long long)b / d * x % m << endl;
    }
}
int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while (T --) solve();
    return 0;
}
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
37
38
39
40
41

中国剩余定理