照常做笔记方便复习

这里用到的一些数学知识的证明都可以在这里找到：OI Wiki

玄学 数学知识笔记（二）：

8.欧拉函数

这回恐怕大家小学二年级还没有学过欧拉函数，就给大家发一下三年级课本

欧拉函数的定义：

$1 \sim N$中与$N$互质的数的个数被称为欧拉函数，记为 $\phi (N)$。
若在算数基本定理中，$N=p_1^{a_1}p_2^{a_2}···p_k^{a_k}$，则：
$\phi(N)=N\times\frac{p_1-1}{p_1}\times\frac{p_2-2}{P_2}\times···\times\frac{p_k-1}{p_k}$

求的过程首先是分解质因数，相信大家都很熟悉，其余的没什么技术难度了，注意开LL。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int main()
{
    int n, x;
    cin >> n;
    while (n -- )
    {
        cin >> x;

        LL ans = x;
        for (int i = 2; i <= x / i; i ++ )
            if (x % i == 0)
            {
                ans = ans  * (i - 1) / i;
                while (x % i == 0) x /= i;
            }
        if (x > 1) ans = ans * (x - 1) / x;

        cout << ans << endl;
    }

    return 0;
}

9.筛法求欧拉函数

对于一个给定的 $n$ 求 $1 \sim n$

的欧拉函数之和，这里显然用上面的方法一个个地分解质因数必会超时，这里就引进了一种线性筛法，

在筛质数的同时统计出每个数的欧拉函数，累加起来即可，具体看代码及其注释：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

typedef long long LL;

int primes[N], phi[N], cnt;
bool st[N];

LL get_eulers(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i, phi[i] = i - 1;//根据定义很显然质数与该数之前的所有数都互质，故为i- 1 
        for (int j = 0; j < cnt && primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)//当这个条件满足时，根据我们之前所学的质数筛法，此时pj为i的最小质因子 
            {
                phi[i * primes[j]] = phi[i] * primes[j];
                //也就是说 i * pj 与 i 之间的差距只有一个 pj，且i的欧拉函数中已经算过这一项了
                //故它们只有公式中第一项的差距，即一个是 i * pj, 一个是 i, 得到该转换式 
                break;
            }
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            // 还是一样 i * pj 与 i 之间的差距只有一个 pj, 但是这里 pj 并不是 i 的一个质因子 故
            //  (pj - 1) / pj 这一项在 phi(i) 中是没有的，结合上面的式子，
            // 则 phi(i * pj) = phi(i) * (pj - 1) / pj * pj     化简之后得上述式子 
        }
    }

    LL res = 0;
    for (int i = 1; i <= n; i ++ ) res += phi[i];
    return res;
}

int main()
{
    int n;

    cin >> n;

    cout << get_eulers(n) << endl;

    return 0;
}

这里顺便提一下y总讲的 欧拉定理（恕我确实没听懂证明的部分），这里只能给出定理内容了
对于一对互质的正整数 $a, n$，则我们有：
$$a^{\phi(n)} \equiv 1 (mod\space n)$$
特别地，当我们的 $n$ 为一个质数 $p$ 时，根据 $\phi(p)=p-1$ 可得：
$$a^{p-1}\equiv1(mod\space p)$$
这就是我们著名的 费马小定理 ，有兴趣的话可以自行百度一下

10.快速幂

对于求一个a的b次幂，如果采用以前的方法暴力求解，复杂度将为 $O(n)$，当n足够大时就会TLE

所以就有了我们的快速幂，它有点倍增的思想在里面，每次计算都是算的 $n^{2^k}$，故时间复杂度可降为 $O(logn)$

这一块比较简单好理解，我就不再细讲了

Code：

#include <cstdio>
#include <iostream>

using namespace std;

typedef long long LL;

int qmi(int a, int b, int p)
{
    int res = 1;
    while (b)//逐位分解b的二进制位
    {
        if (b & 1) res = (LL)res * a % p;//若当前位为1，则res乘上当前位对应的a的幂
        a = (LL)a * a % p;//a随着b的位数增加
        b >>= 1;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        printf("%d\n", qmi(a, b, p));
    }
    return 0;
}

11.快速幂求(乘法)逆元

当 $m$ 为质数时 $b^{m-2}$ 即为 $b$ 的乘法逆元这一点可以由之前讲到的费马小定理以及简单的同余定理可证得

Code：

#include <cstdio>

using namespace std;

typedef long long LL;

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, p;
        scanf("%d%d", &a, &p);
        if (a % p == 0) puts("impossible");//若a与p不互质则绝对不存在逆元
        else printf("%d\n", qmi(a, p - 2, p));//求出a的(p-2)次幂即为答案
    }
    return 0;
}