|
|
## 欧拉函数专题
|
|
|
|
|
|
### 一、定义
|
|
|
|
|
|
<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;
|
|
|
}
|
|
|
``` |
