## 欧拉函数专题

### 一、定义

<font color='red' size=4><b>定义：欧拉函数是小于$n$的数中与$n$互质的数的数目。</b></font>

例如$\large φ(8)=4$，因为$\large 1,3,5,7$均和$\large 8$互质。
>**解释**：$1$和$8$是互质的。互质是指两个数的最大公约数为$1$，而$1$和$8$的最大公约数就是$1$，因此它们是互质的

### 二、公式
如果$n$的唯一分解式：$$\large n=p_1^{r_1}\cdot p_2^{r_2} \cdot...\cdot p_k^{r_k}$$
有：
$$\large φ(n)= n\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2} \times ...  \times \frac{p_k-1}{p_k}$$


还是上面的栗子：
$$\large 8=2^3$$
$$\large φ(8)=8*(1-\frac{1}{2})=4$$

> <font color='red'><b>小结
>  下面三个公式，都需要依赖唯一分解定理：
> $$\large n=p_1^{r_1}\cdot p_2^{r_2} \cdot...\cdot p_k^{r_k}$$
> * ① 约数个数：只与幂次相关，与质因子无关
    约数个数$=(1+r_1)\times (1+r_2) \times...\times (1+r_k)$  
><br>
> * ② 约数和：与质数子和幂次都相关
>   约数和= $(p_1^0+p_1^1+p_1^2+...+p_1^{r_1}) \times (p_2^0+p_2^1+p_2^2+...+p_2^{r_1}) \times ... \times (p_k^0+p_k^1+p_k^2+...+p_k^{r_k})$
><br>
> * ③ 欧拉函数公式，只与因子相关，与指数无关！
>   欧拉函数=$n\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2} \times ...  \times \frac{p_k-1}{p_k}$
  
</b></font>

### 三、欧拉函数公式证明

欧拉函数的证明是使用的融斥原理，从定义出发：

<font color='red' size=4><b>定义：欧拉函数是小于$n$的数中与$n$互质的数的数目。</b></font>

- ① 对数字$n$进行质因数分解：
$$\large n={p_1}^{r_1} \cdot {p_2}^{r_2} \cdot {p_3}^{r_3} \cdot ... \cdot {p_k}^{r_k}$$

- ② 如果一个数包含了$\large p_1$这个因子，那么它肯定与$n$不互质，因为有$\large p_1$这个公因子嘛，换句话说，就是要想与$n$互质，那么一定不能包含$\large p_1,p_2,...,p_k$这些因子。

 小于$n$的所有数字中，如果它包含了$\large p_1,p_2,...,p_k$这样的因子的话，那么它就与$n$不互质，换句话说，只要把小于$n$之内，所有包含$\large p_1,p_2,..p_k$的数字都干掉，剩下的就是与$n$互质的数。所谓包含$\large p_1,p_2,..,p_k$其实也就是 $\large p_1,p_2,..,p_k$的整数倍。
 
 * 把$\large p_1$的倍数从$\large n$中减去，那需要减去多少个呢？
  
答：$\large \displaystyle \left \lfloor \frac{n}{p_1}  \right \rfloor$个.

> **注**：这里想不明白的话，可以举个栗子：比如$n=10$，$p_1=2$,有几个$p_1$的倍数呢？$5$个!为什么呢？
$$\large \displaystyle \left \lfloor \frac{10}{2}  \right \rfloor=5$$


  - ③ 把$\large p_2,p_3,...,p_k$的倍数都减去吧，分别减去$\large  \left \lfloor \frac{n}{p_2}\right \rfloor$,$\large \left \lfloor \frac{n}{p_3}\right \rfloor$,...,$\large \left \lfloor \frac{n}{p_k}\right \rfloor$个。

 - ④ 这么干是减多了的，比如某个数，是$\large p_2$的倍数，也是$\large p_3$的倍数，就减了两回，还需要再加回来$\large p_i * p_j$的倍数，就是 + $\large \frac{n}{p_1 * p_2}$+ $\large \frac{n}{p_1 * p_3}$+ $\large \frac{n}{p_1 * p_k}$+ ....
 
  -⑤ 将公式$\large \phi(n)=n * (1-\frac{1}{p_1}) * (1-\frac{1}{p_2}) * (1-\frac{1}{p_3}) * ... * (1-\frac{1}{p_k})$展开，发现就是上面的东东了，证毕。
 
 变形：
 $\large \phi(n)=n * (1-\frac{1}{p_1}) * (1-\frac{1}{p_2}) * (1-\frac{1}{p_3}) * ... * (1-\frac{1}{p_k}) \\ 
 \Leftrightarrow   \\
 \phi(n)=n * (\frac{p_1-1}{p_1}) * (\frac{p_2-1}{p_2}) * (\frac{p_3-1}{p_3}) * ... * (\frac{p_k-1}{p_k})$



### 四、求单个数字的欧拉函数
**[$AcWing$ $873$. 欧拉函数](https://www.acwing.com/problem/content/875/)**

```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;

// 求单个数的欧拉函数值
int phi(int x) {
    int res = x;
    // 不要写在i*i<=x, 可能会造成爆int
    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); // 最后一个大因子
    return res;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        printf("%d\n", phi(x));
    }
    return 0;
}
```

### 五、线性筛法求欧拉函数

依托于线性筛法，可以顺带求出欧拉函数值。如果对数论了解更多，会知道线性筛法还可以求出很多其它的东西。

 * $phi[1]=1$。 
   $φ(1)$被**定义**为$1$

对区间内每个数进行分情况讨论：

 - **如果这个数是质数**，那么质数$i$的欧拉函数值是$phi[i]=i-1$
   比如$7$，那么$1-6$当中有多少个数与$7$互质呢？显然$6$个都是嘛。
<br>
 - **如果这个数不是质数**，那么数字$i$在被$primes[j]$尝试筛的过程中：(这里设 $p_j=primes[j]$以简便下面的书写)
  
  #### <font color='red'><b>推论$1$：如果$i\  \% \ p_j = 0$, 那么 $phi[i \times p_j] = phi[i] \times p_j$</b></font>
  
  **证明：**
  $\large \because i={p_1}^{r_1} * {p_2}^{r_2} * {p_3}^{r_3} * ... *{p_j}^{r_j}*...*{p_k}^{r_k}$           **【算术基本定理】**


  $i \times p_j$分解质数因数的结果，只比$i$多分解了一个$p_j$，而 $i \ \% \ p_j = 0$ 说明$i$中存在$p_j$因子，只不过指数增加了$1$个。

 
  $\large \therefore i \times p_j  ={p_1}^{r_1} \times {p_2}^{r_2} \times {p_3}^{r_3} \times ... \times{p_j}^{r_j+1}\times...\times{p_k}^{r_k}$

  $\large \phi{(i)}= i \times (1- \frac{1}{p_1}) \times (1- \frac{1}{p_2}) \times (1- \frac{1}{p_3}) \times ... \times (1- \frac{1}{p_j}) $  **【欧拉公式】**
  
  我们发现，<font color='red'><b>欧拉公式只与质数因子相关，而与质数因子的幂次无关！</b></font> 二者的质数因子没有变化，变化的只是某个质数因子的幂次。所以:
  
  $\large \phi{(i \times p_j)} = i \times p_j \times (1- \frac{1}{p_1}) \times (1- \frac{1}{p_2}) \times (1- \frac{1}{p_3}) \times ... \times (1- \frac{1}{p_j}) =  \phi{(i)} \times p_j  $ 

**证毕**
  

#### <font color='red'><b>推论$2$: 如果$i\  \% \ p_j > 0$, 那么 $phi[i \times p_j] = phi[i] \times (p_j-1)$ </b></font>

**证明：**
$\large \because i={p_1}^{r_1} * {p_2}^{r_2} * {p_3}^{r_3} * ... *{p_k}^{r_k} $

$\large \phi{(i)}= i \times (1- \frac{1}{p_1}) \times (1- \frac{1}{p_2}) \times (1- \frac{1}{p_3}) \times ... \times (1- \frac{1}{p_k})$
    
$p_j*i$分解质数因数的结果，只是比$i$多分解了一个$p_j$，而 $i \ \% \ p_j>0$ 说明$i$中不存在$p_j$这个因子，需要写上去。

$\large p_j \times i ={p_1}^{r_1} \times {p_2}^{r_2} \times {p_3}^{r_3} \times ... \times {p_k}^{r_k} \times {p_j}^{1} $

$\large \therefore \phi{(p_j * i)}= p_j * i * (1- \frac{1}{p_1}) * (1- \frac{1}{p_2}) * (1- \frac{1}{p_3}) * ... * (1- \frac{1}{p_k}) * (1- \frac{1}{p_j}) $

$\large \therefore \phi{(p_j * i)}= p_j \times \phi{(i)} \times (1 - \frac{1}{p_j})  =  \phi{(i)} \times ( p_j -1) $  

**【证毕】**


**[$AcWing$ $874$. 筛法求欧拉函数](https://www.acwing.com/problem/content/876/)**

**$Code$**
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;

// 筛法求欧拉函数
// 这个东西就在欧兰筛的基础上，加上题解中证明的公式，只能是背下来，没有别的办法
int primes[N], phi[N], st[N];
int cnt, res;
void get_eulers(int n) {
    phi[1] = 1; // 1的欧拉函数值是1，这个是递推的起点
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1; // ①质数,则phi(i)=i-1
        }
        for (int j = 0; primes[j] <= n / i; j++) {
            int t = primes[j] * i;
            st[t] = 1;
            if (i % primes[j] == 0) {
                phi[t] = phi[i] * primes[j]; // ② i%pj==0
                break;
            } else
                phi[t] = phi[i] * (primes[j] - 1); // ③i%pj>0
        }
    }
}

signed main() {
    int n;
    cin >> n;
    // 筛法求欧拉函数
    get_eulers(n);
    // 累加欧拉函数值
    for (int i = 1; i <= n; i++) res += phi[i];
    printf("%lld\n", res);
}
```
### 六、欧拉定理
 $n$ 和 $a$ 为正整数，且 $n$,$a$  互素，即$gcd(n,a)=1$，则：

 $$a^{\phi(n)} \equiv 1 (mod \ n)$$

> **[讲解视频](https://www.bilibili.com/video/BV1tK411f78z)**
> 证明挺麻烦的，有兴趣可以看一看，我就不证明了~

####　用途
这个定理可以用来 **简化幂的模运算**。

#### 基本例子
比如计算$7^{222}$的个位数，实际是求$7^{222}$被$10$除的余数。$7$和$10$ **互素** ，且$φ(10)=4$。由欧拉定理知
$$7^4 \equiv 1(mod \ 10) \ (a=7,n=10)$$

所以$7^{222}=(7^4)^{55}*7^2 \equiv 1^{55}*7^2 \equiv 49 \equiv 9 (mod \ 10)$

所以，答案是$9$。


#### 复杂例子

求$3333^{5555}$的 **个位** 是什么。

很明显不可能直接把$3333^{5555}$的结果计算出来，那样太大了。但我们想要确定的是$3333^{5555} \%10 $，问题就简单了:

- 我们知道 $3333^{5555} \%10 $= $3^{5555}\%10$ 

$\\$

- 因为要求的是末位，也就是$\%10$的结果，想要使用  **欧拉定理**:
  - $3$与$10$互质
  - $\phi(10)=4$,需要想办法构造$5555$里面有多少个$4$，可以直接把$4$的倍数直接约掉:
  \
  根据 **模运算规则** $(a * b) \% p = (a \% p * b \% p) \% p$ ，由于$5555 = 4 * 1388 + 3$，我们得到
  \
  $3^{5555}\%10=(3^{4*1388} * 3^3)\%10=(3^{4*1388}\%10* 3^3\%10)\%10=(3^{4*1388}\%10* 27\%10)\%10=(3^{4*1388}\%10* 7)\%10$
  \
  **欧拉定理** 出场!
  \
  对于$3^{4*1388}$而言，  $3^{4*1388} = (3^4)^{1388}$    
  \
  $(3^4)$中$\phi(n) =\phi(10)= 4$,即 $n = 10$($1，3，7，9$满足);
  \
  同时 满足 $3$和$10$互质，所以 $3^{4*1388}=(1\%10)^{1388} = 1$
  \
  所以$(3^{4*1388}\%10* 7)\%10= (1 * 7) \% 10 = 7$
  \
  计算完毕,答案是$7$。
### 七、一些性质

#### 性质$1$
当 $gcd(n,m)=1$时， $$\large \phi(nm)=\phi(n) \times \phi(m)$$ 

从定义上来证明：

假设有两个互质的正整数$n,m$，则
$$\large \phi(n)=n \prod (1-\frac{1}{p_i}) $$
$$\large \phi(m)=m \prod (1-\frac{1}{p_i'}) $$
$$\large \phi(n)\times \phi(m)=n \prod (1-\frac{1}{p_i}) \times m \prod (1-\frac{1}{p_i'})=nm \prod(1-\frac{1}{p_i}) \prod(1-\frac{1}{p_i'}) $$

因为$n,m$互质，所以$p_i$和$p_i′$各各都不相同，且都是$n,m$的质因子
因此就可以推出$φ(nm)=φ(n)φ(m)$

至此，积性函数的性质得证。但是由上面的证明可知，$n,m$必须要互质才可以满足欧拉函数是 **积性函数**，由此可见 **欧拉函数不是完全积性函数**

#### 性质$2$
当 $n$ 为奇数时, $\phi(2*n)=\phi(n)$

**证明**
根据上面的性质$2$,当 $n$ 为奇数时， $n$ 与 $2$ 互质，
$$\large \phi(2*n)=\phi(2)\times \phi(n)$$

又因为$$\large \phi(2)=1$$
所以 $\large \displaystyle \phi(2*n)=\phi(n)$

#### 性质$3$
若 $n=p^k$ ， 则 $\large \phi(n)=p^k*\frac{p-1}{p}=p^k-p^{k-1}=p^{k-1}(p-1)$

#### 性质$4$
<font color='red'><b>当$n>2$时，所有小于$n$且与$n$互质的数和$\large \displaystyle =\frac{n \times \phi(n)}{2}$,并且$\phi(n)$ 为偶数
</b></font>

**证明**
需要知道的一个基本事实是 $gcd(n,x)=gcd(n,n-x) \ \ \ \ (n>x)$
> **注**：关于这个，可以了解一下 **[更相减损术](https://link.zhihu.com/?target=https%3A//baike.baidu.com/item/%25E6%259B%25B4%25E7%259B%25B8%25E5%2587%258F%25E6%258D%259F%25E6%259C%25AF/449183%3Ffr%3Daladdin)**
> 也可以证明一下：
> 反证法，假设$n$与$x$互质，$n$与$n-x$不互质
设$n$和$n-x$的最大公约数为$m$，则$n=p*m，n-x=q*m$
所以$x=(p-q)*m$，推导出$x$和$n$有公约数$m$，**与假设矛盾**


因为 $gcd(n,x)=gcd(n,n-x)(n>x)$ ，所以与$n$互质的数都是 **成对出现** 的

每一对的和都为 $n$ 。所以他们的和为 $\phi(n) \times n \div 2 $ 。

至于 $\phi(n)(n>2)$ 为偶数。因为与 $n$互质的数都是成对出现的，所以显然与 $n$互质的数为偶数，即 $\phi(n)$ 为偶数。

#### 性质$5$
若 $p|n$ 且 $p^2|n$ ，则
$$\large \phi(n)=\phi(\frac{n}{p})* p$$
若$p \mid n$且$p^2 \nmid n$,则$$\large \displaystyle \phi(n)=\phi(\frac{n}{p})*(p-1)$$

**证明**
对于第一点
若 $p \mid n$ 且 $p^2 \mid n$ ，则证明 $n$ 和 $\frac{n}{p}$ 有相同的质因子，只是 $p$ 这一项的指数不同

那么我们可以将其按照欧拉函数的计算式展开，并相除，可得：
$$\large \frac{n\prod_{i=1}^{m}(1-\frac{1}{p_i})}{\frac{n}{p}\prod_{i=1}^{m}(1-\frac{1}{p_i})}=\frac{n}{\frac{n}{p}}=p $$

对于第二点
若 $p \mid n$ 且 $p^2 \nmid n$ ，则说明 $p$ 与 $\frac{n}{p}$ 互质（因为 $p$ 为素数）

那么根据欧拉函数为积性函数的这个性质即可证得
$$\large \phi(n)=\phi(\frac{n}{p})*\phi(p)=\phi(\frac{n}{p})*(p-1)$$

证毕。

> **注**： 这个性质广泛用于递推求欧拉函数,也就是筛法求欧拉函数的基础。

#### 性质$6$
设$\large n$为一个正整数 ,$\large \displaystyle n=\sum_{d \mid n}\phi(d) $

**证明**
列出
$$\large \frac{1}{n},\frac{2}{n},\frac{3}{n},...,\frac{n}{n},$$
一共 $n$个分数，再将他们化简．

最简分数$\large \displaystyle \frac{a}{b}$在上面出现的话，当且仅当 $b|n$且$gcd(a,b)=1$。
那么以$b$为分母的分数共$ϕ(b)$个。

分母一共被划分为 $\large \displaystyle \sum_{d \mid n}1$份．

所以
$$\large \displaystyle n=\sum_{d \mid n}\phi(d) $$


### 七、习题
**[$HDU$ $3501$ $Calculation$ $2$](https://acm.hdu.edu.cn/showproblem.php?pid=3501)**

**题意**：给定整数$n$，求$[1,n]$中与$n$ **不互质** 的数的和，最后$mod\ 1e9+7$


看一下上面的性质$4$证明,我们知道:设$t$为$[1,n]$中与$n$互质的数的和
$$\large  t =\frac{n \times \phi(n)}{2}$$

我们利用欧拉函数和欧几里德定理，`if gcd(n,i)==1`，则有 `gcd(n,n-i)==1` ，可以知道其中一个若为$i$,则存在一个为$n-i$, 那么二者之和为$n$  ，这样的一共有$\phi(n)/2$对, 故与$n$互质的所有数的和为 $n \times \phi(n)/2$ ,那么与$n$ **不互质**的数就是

$$\large n \times (n-1)/2-n \times \phi(n)/2$$

```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int MOD = 1e9 + 7;

// 求单个数值的欧拉函数值
int phi(int 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);
    return res;
}

signed main() {
    int n;
    while (cin >> n && n) {
        // 小于n的数字中有多少个数字与n互质
        int ans = n * (n - 1) / 2;          // 高斯公式，(首页+末项)*项数/2
        ans = (ans - phi(n) * n / 2) % MOD; // 扣除掉 phi(n)*n/2
        cout << ans << endl;
    }
}

```

**[$BZOJ$ $3884$ 上帝与集合的正确用法](https://www.lydsy.com/JudgeOnline/problem.php?id=3884)**

```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;

// https://blog.csdn.net/skywalkert/article/details/43955611
// https://www.cnblogs.com/shuguangzw/p/5697183.html
// 指数循环节问题
// https://blog.csdn.net/acdreamers/article/details/8236942
map<int, int> f;
int pow(int x, int k, int p) {
    int ret = 1;
    while (k) {
        if (k & 1)
            ret = (long long)ret * x % p;
        x = (long long)x * x % p;
        k >>= 1;
    }
    return ret;
}
int phi(int x) {
    int ret = x;
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0) {
            ret -= ret / i;
            while (x % i == 0)
                x /= i;
        }
    if (x > 1)
        ret -= ret / x;
    return ret;
}
int F(int x) {
    if (f.count(x))
        return f[x];
    int p = phi(x);
    return f[x] = pow(2, F(p) + p, x);
}
int main() {
    int t, n;
    scanf("%d", &t);
    f[1] = 0;
    while (t--) {
        scanf("%d", &n);
        printf("%d\n", F(n));
    }
    return 0;
}
```