数论——欧拉函数的自闭

啊上一期点赞是迅速的过了$5$，咱们这期要求也不高：

点赞 + 收藏过$10$马上更新。

上次的同余方程

上次的贴过原题了，这次就不贴了。
好吧还是贴一下吧，方便后面证明。
简化题意：给定$a, b, m$，求一个$x$，使得$a\times x \equiv b(\mod m)$
随意输出任意一组解即可。
那这个怎么解呢？

遇到方程走三步

变形方程，部分求解，回归整体

第一步：变形方程

原式可以变为：
$a \times x = m \times y + b$
此时存在一个整数$y$，使得上边的代数式成立。
那么还可以再次变形成：
$a \ times x - m \times y = b$
看着是不是莫名熟悉？
再稍微改一下就行了。
令$y’$ = $-y$
然后就是exgcd了。
$a \times x - m \times y’ = b$
那他有解的条件就是$b$必须整除$gcd(a, m)$。
也就是说，如果上面的条件成立，那就一定有解。

第二步：部分求解

这一步我们需要把$x$和$y’$求出来，所以说是部分求解。
那这里就使用扩展欧几里得算法求解即可。

第三步：回归整体

然后用$y’$算回$y$。
这样就可以得出一个方程：
$a \times x = b + m \times y$
然后就ok了。
代码如下：

#include<iostream>
using namespace std;
int exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int a, b, m;
        cin >> a >> b >> m;
        int x, y;
        int d = exgcd(a, m, x, y);
        if(b % d) puts("impossible");
        else cout << (long long) x * b / d % m << endl;
    }
    return 0;
}

进入正题：欧拉函数

啥是欧拉函数？？？

$N$欧拉函数是指$1-N$中与$N$互质的数的个数。

咋求呢？

先说公式，

前方含有大量$Latex$，可能导致加载过慢，非战斗人员请立即撤离，注意这不是演习！！！

$$ 假设n的分解质因数为：\\\ n = {p_1}^{\alpha_1} \times {p_2}^{\alpha_2} \times {p_3}^{\alpha_3} \times \ldots \times {p_k}^{\alpha_k}\\\ 则\varphi(n) = n \times (1 - \frac 1 {p_1}) \times (1 - \frac 1 {p_2}) \times (1 - \frac 1 {p_3}) \times \ldots \times (1 - \frac 1 {p_1}) \\\ \\\ 懒得分开了，继续证明.jpeg\\\ \\\ 先举个例子试一下。\\\ 6 = 2 \times 3\\\ 那么根据公式，\varphi(6) = 6 \times (1 - \frac 1 2) \times (1 - \frac 1 3) = 6 \times \frac 1 2 \times \frac 2 3 = 2\\\ 然后证明。\\\ 用到了容斥原理，这个东西以后再说8。\\\ 1. [1, n] -= (p_1 \times 1 + p_1 \times 2 +\ldots + p_1 \times \lfloor {\frac n {p_1}} \rfloor)\\\ + (p_2 \times 1 + p_2 \times 2 +\ldots + p_2 \times \lfloor {\frac n {p_2}} \rfloor) \ldots (p_k \times 1 + p_k \times 2 +\ldots + p_k \times \lfloor {\frac n {p_k}} \rfloor)\\\ 上面那行Latex翻脸不认人。\\\ 更新集合后我们叫他S_1\\\ 2. S_1 += ((p_i \times p_j \times 1 + p_i \times p_j \times 2 +\ldots\\\ + p_i \times p_j \times \lfloor {\frac n {p_i \times p_j}} \rfloor)) (注：i,j为[1, k]中的两个数)\\\ 更新上面的集合为S_2\\\ 3. S_2 -= ((p_i \times p_j \times p_l \times 1 + p_i \times p_j \times p_l \times 2 +\ldots\\\ + p_i \times p_j \times p_l \times \lfloor {\frac n {p_i \times p_j \times p_l}} \rfloor)) (注：i,j,l为[1, k]中的三个数)\\\ \ldots\\\ 用式子表示出来就是：n - \frac n {p_1} - \frac n {p_2} - \ldots - \frac n {p_k}\\\ + \frac n {p_1 \times p_2} + \frac {p_1 \times p_3} + \ldots + \frac n {p_{k - 1} \times p_k}\\\ - \frac n {p_1 \times p_2 \times p_3} - \frac n {p_1 \times p_2 \times p_4} - \ldots - \frac n {p_{k - 2} \times p_{k - 1} \times p_k} \ldots\\\ 接着我们发现，按照\varphi(n) = n \times (1 - \frac 1 {p_1}) \times (1 - \frac 1 {p_2}) \times (1 - \frac 1 {p_3}) \times \ldots \times (1 - \frac 1 {p_1}) \\\ 这个式子展开后和刚刚得出的一样，ok搞定。\\\ emm，我闻到了CPU的香味。\\\ $$

继续，那我们改如何实现呢？
先贴上题。

给定n个正整数ai，请你求出每个数的欧拉函数。

欧拉函数的定义
$1 ~ N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记$ϕ(N)$。
若在算数基本定理中，$N={p_1}^{a_1}{p_2}^{a_2}\ldots {p_m}^{a_m}$，则：
$ϕ(N) = N∗\frac {p_1 − 1} {p1} ∗ \frac {p_2−1}{p_2}∗\frac{p_m - 1}{p_m}$

输入格式

第一行包含整数$n$。

接下来$n$行，每行包含一个正整数$a_i$。

输出格式

输出共$n$行，每行输出一个正整数$a_i$的欧拉函数。

数据范围

$1 ≤ n ≤ 100,$
$1 ≤ a_i \times 10^9$

输入样例：

3
3
6
8

输出样例：

2
2
4

代码

这里直接贴代码了，就是套用了一下公式，数学章的代码实现起来都不是很难，主要在于公式的推导和证明。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int x;
        cin >> x;
        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);
        cout << res << endl;
    }
    return 0;
}

好了今天的分享就到这里了。

这是我的全部分享

bye~

下次聊筛法求欧拉函数，不见不散！！！（