本节课仍然偏重于数学推导，请大家做好心理准备。

因为数学这一章基本都是这样，特别偏数学推导，因为这一章的题目能不能做出来，基本取决于大家的数学功底，和编程的功底关系可能并没有那么大。

1、欧拉函数

$\varphi(n)$：表示 $1$ ~ $n$ 中与 $n$ 互质的数的个数。

比如 $\varphi(6)=2$，$1$ 2 3 4 $5$ 6。

这是欧拉函数的定义，那么怎么求欧拉函数呢？

假如 $N$ 分解质因数之后的结果是 $N=P_1^{\alpha 1}P_2^{\alpha 2}···P_k^{\alpha k}$，那么 $\varphi(N)=N(1-\frac{1}{P_1})(1-\frac{1}{P_2})···(1-\frac{1}{P_k})$，这是 $\varphi(n)$ 的一个公式。

例如：$N=6=2*3$，$\varphi(n)=6*(1-\frac{1}{2})(1-\frac{1}{3})=2$。

证明：容斥原理（下节课再讲，这里会用到我们的容斥原理）

这节课我们会把数论讲完，下节课会讲高斯消元、组合计数和容斥原理。这节课我们就直接利用容斥原理的结论了，容斥原理的原理的话我们就留到下节课来讲。

思考 $1$ ~ $n$ 中和 $n$ 互质的个数怎么求呢？

（1）从 $1$ ~ $n$ 去掉 $P_1$ ~ $P_k$ 的所有倍数。就是我们先去掉 $P_1$ 的所有的倍数，$P_1$ 的所有的倍数一定是不和 $n$ 互质的，因为它们和 $n$ 有公因子 $P_1$，然后再去掉所有 $P_2$ 的倍数，一直去到所有 $P_k$ 的倍数。

那么我们的公式就是 $N-\frac{N}{P_1}-\frac{N}{P_2}-···-\frac{N}{P_k}$，注意 $N$ 一定要整除。那这里面一定会多去一部分，比如说一个数既是 $P_1$ 的倍数又是 $P_2$ 的倍数，那么它就会被去两次，但是我们应该去一次，所以说我们就会多去一次，所以说第二步就需要把多去的数加回来。

（2）加上所有 $P_i*P_j$ 的倍数，$i$ 和 $j$ 就是从 $P_1$ ~ $P_k$ 中任取两个数，因为所有 $P_1$ ~ $P_k$ 的倍数都被减了两次，但是我们只能减一次，所以公式里就是 $N-\frac{N}{P_1}-\frac{N}{P_2}-···-\frac{N}{P_k}+\frac{N}{P_1P_2}+\frac{N}{P_1P_3}+···$，把所有两个质数的组合都给它加上。

那么这里又会有一个问题，如果说这个数同时是 $P_1$、$P_2$、$P_3$ 的倍数的话，那么它会先被 $P_1$ 减一次，再被 $P_2$ 减一次，再被 $P_3$ 减一次，再被 $P_1P_2$ 加一次，$P_1P_3$ 加一次，$P_2P_3$ 加一次，那么会再加上三次。

效果就是中心没有减没有加，但其实我们要把它去掉，所以在这里我们需要把所有 $P_i*P_j*P_k$ 的倍数减去。

（3）减去所有 $P_i*P_j*P_k$ 的倍数，也就是减去所有三个质数的乘积的倍数。$N-\frac{N}{P_1}-\frac{N}{P_2}-···-\frac{N}{P_k}+\frac{N}{P_1P_2}+\frac{N}{P_1P_3}+···-\frac{N}{P_1*P_2*P_3}-\frac{N}{P_1*P_2*P_4}-···$，那么大家找一下规律，即减去一个质数分之N，加上两个质数的乘积分之N，减去所有三个质数的乘积分之N，那么下一个就应该是加上所有四个质数的乘积分之N，$N-\frac{N}{P_1}-\frac{N}{P_2}-···-\frac{N}{P_k}+\frac{N}{P_1P_2}+\frac{N}{P_1P_3}+···-\frac{N}{P_1*P_2*P_3}-\frac{N}{P_1*P_2*P_4}-···+\frac{N}{P_1*P_2*P_3*P_4}-···$，然后再减去所有五个质数之之N，以此类推，这个就被称为容斥原理。

所以 $1$ ~ $n$ 中所有和 $n$ 互质的个数应该是 $N-\frac{N}{P_1}-\frac{N}{P_2}-···-\frac{N}{P_k}+\frac{N}{P_1P_2}+\frac{N}{P_1P_3}+···-\frac{N}{P_1*P_2*P_3}-\frac{N}{P_1*P_2*P_4}-···+\frac{N}{P_1*P_2*P_3*P_4}-···$ 这一坨，如果把 $\varphi(N)=N(1-\frac{1}{P_1})(1-\frac{1}{P_2})···(1-\frac{1}{P_k})$ 这个式子展开就会发现这两个式子是相等的。

我们可以简单的看一下上面这个式子，可以先把 $N$ 全部提到前面去，那么这里展开的 $\frac{1}{P_1}$ 的系数是多少呢？即 $(1-\frac{1}{P_1})$ 这一项选一个 $P_1$，其它都选 $1$，所以 $\frac{1}{P_1}$ 的系数是 $-1$，那 $\frac{N}{P_1P_2}$ 的系数是多少呢？是 $(1-\frac{1}{P_1})(1-\frac{1}{P_2})$，然后全部选 $1$，它的系数是 $+1$，因此我们发现把公式展开和我们的容斥原理是完全相等的，然后容斥原理得到的这个式子就可以求出来 $1$ ~ $n$ 当中所有质数的个数，所以说这个式子就是求的 $1$ ~ $n$ 当中所有质数的个数了。

这就是用容斥原理的一个证明，接下来我们看一下代码怎么写？

题目：给定 $n$ 个正整数 $a_i$，请你求出每个数的欧拉函数，$1≤n≤100,1≤a_i≤2×10^9$。

思路：直接套公式来求就可以了，用这个公式来求的时间复杂度是多少呢？它的瓶颈就在分解质因数上，然后分解质因数我们前面讲过，它的时间复杂度是 $\sqrt n$，因此用这个公式来求它的时间复杂度是 $\sqrt n$，这个题有 $n$ 个数，那么时间复杂度就是 $n*\sqrt a_i$，根号一下就是四万到五万之间，那 $100$ 个四万到五万之间，所以我们的时间复杂度就是 $400$ 万 ~ $500$ 万之间，是可以接受的。

然后我们来写一下代码，实际上就从定义出发就可以了：

首先我们回忆一下分解质因数是怎么写的，然后我们套一下公式就可以了。

#include <bits/stdc++.h>
using namespace std;

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
        	// res = res * (1 - 1 / i); 不能存小数，所以要化简一下，先除 i 再乘 （i - 1） 就可以了 
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}


int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        cout << phi(x) << endl;
    }

    return 0;
}

这个就是我们用公式求欧拉函数。应用场景的话先不用管，我们待会会讲，后面有一个例子是讲欧拉函数是干嘛的。欧拉函数的用法其实就是我们的欧拉定理，我们待会讲欧拉定理的证明。其实我们只要知道欧拉函数的公式就可以了，然后知道这个公式的推导用的是容斥原理就可以了。

然后我们来看下一个问题，用筛法来求欧拉函数。因为目前我们是用公式来求某一个数的欧拉函数，但在有些情况下我们需要求出来 $1$ ~ $n$ 中每一个数的欧拉函数，$1≤n≤10^6$。如果用公式来做的话，那么要把每个数都分解质因数，那么时间复杂度就会变成 $N*\sqrt n$，非常的慢，然后我们可以借助我们的线性筛法求素数的代码，可以用 $O(n)$ 的时间计算出来每一个数的欧拉函数，所以就很强大了。

如何求呢？在求之前我们先回顾一下线性筛法：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1000010;

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

void get_eulers(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;
        }
    }
}


int main()
{
    int n;
    cin >> n;

    get_eulers(n);

    cout << res << endl;

    return 0;
}

然后我们来看一下如何在我们的代码当中求得我们的欧拉函数。其实线性筛法这个代码是很好用的，它可以顺便求出来很多东西，如果大家对数论了解比较多的话，就知道可以顺便求出来很多东西。

首先如果这个数是质数的话，它的欧拉函数是多少？比如说一个质数 $P$，那么它的定义是 $1$ ~ $P$ 中有多少个数与 $P$ 互质，显然 $1$ ~ $P-1$ 都是与 $P$ 互质的。

如果 i % primes[j] == 0 的话，那么 primes[j] * i 这个数的欧拉函数是多少呢？如果 i % primes[j] == 0，那么 $pj$ 是 $i$ 的一个质因子，那么在求 $\varphi(i)$ 的过程当中就已经乘过了一个 $(1-\frac{1}{pj})$ 了，那么我们来看一下求 $\varphi(pj*i)$ 和 $\varphi(i)$ 之间有什么关系？因为 $\varphi(pj*i)$ 只比 $\varphi(i)$ 多了一项，就乘了一个 $pj$ 而已，那么 $pj*i$ 它的一个分解质因数之后的一个结果只是比 $i$ 分解质因数的结果多乘了一个 $pj$，又有 $pj$ 是 $i$ 的一个质因子，所以说在 $\varphi(i)$ 的表达式里就已经乘过了一个 $(1-\frac{1}{pj})$ 了，因此我们 $pj*i$ 的所有质因子都是在 $i$ 中出现过的，即 $pj*i$ 和 $i$ 的所有质因子是相同的，因为 $pj$ 也是一个质因子，那么 $\varphi(i)=i(1-\frac{1}{P_1})(1-\frac{1}{P_2})···(1-\frac{1}{P_k})$，$\varphi(pj*i)=pj*i*(1-\frac{1}{P_1})(1-\frac{1}{P_2})···(1-\frac{1}{P_k})$，所以 $\varphi(pj*i)=pj*\varphi(i)$，我们就推出来了。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1000010;

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

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


int main()
{
    int n;
    cin >> n;

    get_eulers(n);

    cout << res << endl;

    return 0;
}

第二种情况就是 i % primes[j] != 0 ，那么 $pj$ 一定是 $i$ 的一个最小质因子，而且 $pj$ 还不不包含在 $i$ 的质因子当中的，那么 $\varphi(i)=i(1-\frac{1}{P_1})(1-\frac{1}{P_2})···(1-\frac{1}{P_k})$，那么 $pj*i$ 的所有质因子应该是比 $i$ 的所有质因子多了一个 $pj$，其余都完全一样，因此 $\varphi(pj*i)=pj*i*(1-\frac{1}{P_1})(1-\frac{1}{P_2})···(1-\frac{1}{P_k})(1-\frac{1}{P_j})$，$\varphi(pj*i)=pj*\varphi(i)*(1-\frac{1}{P_j})=\varphi(i)*(p_j-1)$，即 $\varphi(pj*i)$ 是 $\varphi(i)$ 的的 $P_j-1$ 倍。

最后再算一下总和。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1000010;

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

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


int main()
{
    int n;
    cin >> n;

    get_eulers(n);

    cout << res << endl;

    return 0;
}

那么这个就是在求线性筛法的过程当中，把每个数的欧拉函数求一遍。建议大家课后自己推一遍。这节课比较偏数学，大家学起来可能比较吃力，没关系，大家自己课后推一遍就好了。

欧拉函数的作用在欧拉定理，这里我们简单的把欧拉定理讲一下：

欧拉定理：如果说 $a$ 与 $n$ 互质，则有 $a^{\varphi(n)}\equiv1\ (mod \ n)$，比如说 $a=5$，$n=6$，$5$ 和 $6$ 互质，那么 $5^{\varphi(6)}\ mod \ 6=5^2\ mod \ 6\equiv1$，这就是我们的欧拉定理。

证明：假设 $1$ ~ $n$ 中所有和 $a$ 互质的数一共是 $a_1$，$a_2$，···，$a_{\varphi(n)}$，一共 $\varphi(n)$ 个数，由于 $a$ 和 $n$ 是互质的，所以 $aa_1$，$aa_2$，···，$aa_{\varphi(n)}$ 这每一个数也都是和 $n$ 是互质的，因为 $a$ 和 $n$ 是互质，每一个 $a_i$ 也和 $n$ 互质，所以两个数的乘积也和 $n$ 互质，而且这 $\varphi(n)$ 个数两两都不相同。

反证法：假设 $a_i$ 和 $a_j$ 是相同的，$aa_i\equiv aa_j\ (mod \ n)$，那么 $a*(a_i-a_j)\equiv0\ (mod \ n)$，由于 $a$ 和 $n$ 是互质的，那么 $a_i\equiv a_j\ (mod \ n)$，所以错误。

而 $1$ ~ $n$ 中所有和 $a$ 互质的数只有 $\varphi(n)$ 个，因此这 $a_1$，$a_2$，···，$a_{\varphi(n)}$ $\varphi(n)$ 个数和这 $aa_1$，$aa_2$，···，$aa_{\varphi(n)}$ $\varphi(n)$ 个数就是一组数，只不过顺序变了一下，那么它们的乘积也是相同的，就是重排序的一个结果，很神奇啊。

那么 $a^{\varphi(n)}*(a_1*a_2···*a_{\varphi(n)})\equiv a_1*a_2···$ $*a_{\varphi(n)}\ (mod \ n)$，那么 $a^{\varphi(n)}\equiv1\ (mod \ n)$。

那么这就是一个欧拉定理的证明，这里并没有用到什么高深的知识，都是用的一些基础知识，这样我们就把欧拉定理证完了。大家课后把这个过程推一遍，推的思路大家下来可以看一下录像，推的话大家跟着录像画一遍就可以了，没那么难，就学数学一定不能空想，一定要自己推一遍，而且是真的自己把公式推一遍，而不是把老师的公示抄一遍，这样是没有效果的，代码的话把老师的代码抄一遍它是有效果的，但公式的话没用，必须要自己想，推一遍才可以。

欧拉定理有一个简单的推论，如果 $n$ 是质数的时候，$a^{\varphi(p)}\equiv1\ (mod \ p)$，那么 $a^{p-1}\equiv1\ (mod \ p)$，这就是欧拉定理的一个简化版，被称为费马定理，也很简单就可以被证出来。

这就是一个欧拉定理和费马（小）定理的证明，后面我们会用到这样一个定理。我们继续往后看，大家不要急，看下一个内容。

很简单对吧，数论也没那么难，很简单，但一定要自己推一遍，如果干听我讲的话，应该和听天书差不多。

竞赛的时候是不会考证明的，大家要清楚这一点，但如果会证明的话，会对来龙去脉搞的更清楚一点，而且也可以装逼了对不对。

2、快速幂

用来解决什么问题呢？快速的求出来 $a^k\mod p$ 的结果，在 $O(\log k)$ 的时间复杂度内，$1≤a,p,k≤10^9$，如果暴力用循环来做，就要写成循环 $k$ 次

res = 1;
for (int i = 1; i <= k; i ++ )
	res = res * a % p;

时间复杂度就是 $O(k)$ 的，太慢了，快速幂可以做到 $O(\log k)$，$10^9$ 大纲就是 $30$ 次就可以做出来，这个就很恐怖了。

核心思路：反复平方法

先预处理出来 $a^{2^0}\mod p$、$a^{2^1}\mod p$、$a^{2^2}\mod p$···$a^{2^{\log k}}\mod p$ 的结果，一共是 $\log k$ 个，把这些值预处理出来之后，如何把 $a^k$ 组合出来呢？其实只需要把 $a^k$ 拆成若干个我们前面预处理出来的数的乘积就好了。

$a^k=a^{2^{x_1}}*a^{2^{x_2}}*···*a^{2^{x_t}}=a^{2^{x_1}+2^{x_2}+···+2^{x_t}}$，所以说我们的目标是把 $k$ 拆成前面 $2^0$、$2^1$、···$2^{\log k}$ 这 $\log k$ 个中若干个数的和，这个就太简单了，直接把 $k$ 换成二进制就可以了。

比如 $(k)_{10}=(110110)_2$，那么 $k=2^1+2^2+2^4+2^5$，所以这个是一定可以成立的。

那么把 $k$ 拆成前面 $2^0$、$2^1$、···$2^{\log k}$ 这 $\log k$ 个中若干个数的和，这个就分解下质因数就可以了，二进制是 $1$ 的位就把它加上就可以了。

整个的计算量就是 $\log k$，首先预处理的时间复杂度是 $\log k$，然后在计算的时候做多是拆成 $\log k$ 个数相加，那么两步加在一块，整个的时间复杂度就是 $O(\log k)$，这就很简单。

如何预处理出来 $\log k$ 个数呢？其实每一个数都是上面这个数的平方模 $p$：所以我们平方 $k$ 次就可以把这 $\log k$ 个数预处理出来了。

然后我们来举一个例子，不然太抽象，大家搞不明白。

比如要算 $4^5 \mod 10$ 的结果，

这就是快速幂的一个基本思路，也叫欧拉降幂。

虽然思路看起来很乱，但代码巨短，这个写起来和快排是类似的，就思路有很多边界问题，但代码的话，根据前人的积累，有很多极简的写法，所以推荐给大家，那么我们来看一下代码是怎么写的，快速幂是一个用的非常多的算法，数论里面的常客。

题目：给定 $n$ 组 $a_i,b_i,p_i$，对于每组数据，求出 $a^{b_i}_i\mod p_i$ 的值，$1≤n≤100000,1≤ai,bi,pi≤2×10^9$。

因为模的数是 $10^9$， 我们发现里面有乘积，两个 $10^9$ 相乘会爆 int，所以我们这里要用 long long，数论里的很多题都要用 long long。

并且读入的数据比较多，我们建议大家用 scanf 来读。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
// a^k % p
LL qmi(int a, int k, int p)
{
    LL res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p; // 当前k的末位是1 
        k >>= 1; // 把 k 的末位删掉 
		a = (LL)a * a % p; // 再把a变成下一个，平方一下 
    }
    return res;
}


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

    return 0;
}