隐藏
「bzoj3884」上帝与集合的正确用法 - 扩展欧拉定理 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bzoj3884」上帝与集合的正确用法 - 扩展欧拉定理

题目大意

    求无限个$2$:

    的值。


吐槽

个人觉得这道题是错题,虽然作为一道扩展欧拉定理的联系题来讲还是很不错的。

首先显然可知$2^{2^{2^{2^\cdots}}}$趋近于无穷,而无穷模一个数是无意义的。
证明如下:
假设无穷满足模的性质,则$+\infty\bmod x=y(y\lt x)$,因此$+\infty=kx+y$。
这显然是不现实的,故可知$+\infty$模一个数无意义。

以下将本题作为一道扩展欧拉定理的练习题讲述而不进行深究。


题目分析

根据扩展欧拉定理,当$x\ge\varphi(m)$:

令$a=2,x=2^{2^{2^{\cdots}}}$,显然满足$x\ge\varphi(m)$。
因此套用扩展欧拉定理得到:

而我们发现$2^{2^{2^{\cdots}}}\bmod\varphi(m)$与$2^{2^{2^{\cdots}}}\bmod m$是同一种形式,因此可以递归。

而递归的过程耗时$O(\log m)$的,下面我们来证明这个时间复杂度。
引入一个结论:

对于任意一个正整数$x(x\gt2)$,满足$\varphi(x)$是偶数。

证明:
对$x$进行分解,$x=\prod_{i=1}^kp_i^{a_i}$,其中$p_i$是素数。
根据欧拉函数的计算式$\varphi(x)=x\prod_{i=1}^k\frac {p_i-1}{p_i}$(证明见这里),对$x$分类讨论。

  • $x$是以$2$为底的幂$2^y$
    后半部分$\prod_{i=1}^k\frac {p_i-1}{p_i}=\frac12$,而$x$是$2^y(y\gt1)$,因此$\varphi(x)$是偶数。
  • $x$不是$2^y$
    $x$必定存在一个$\gt2$的奇素数$p_i$。
    • 若$x$是奇数,则$\prod_{i=1}^k\frac {p_i-1}{p_i}$是偶数。
    • 若$x$是偶数,则$x$含有偶素数$2$,而$x$也含有$2$,两者抵消,所以$\varphi(x)$仍然是偶数。

Q.E.D.

我们再引入一个结论:

当$x$是偶数的时候,$\varphi(x)\le\frac x2$。

由$\varphi$的计算式显然。

因此,而若$x$是一个$\neq1$的奇数,$\varphi(x)$即是一个偶数。
故$x$经过$O(\log x)$次$x=\varphi(x)$的操作即可变为$1$。
时间复杂度证毕。

若每次暴力求欧拉函数,时间复杂度具体我也不会算,但一定比$O(\sqrt m\log m)$小。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

int Quick_Pow(int a,int b,int p) {
int ans=1;
for(; b; b>>=1,a=1ll*a*a%p)if(b&1)ans=1ll*ans*a%p;
return ans;
}

int Phi(int x) {
int sum=x;
for(int i=2; i<=sqrt(x); i++)
if(x%i==0) {
sum=sum/i*(i-1);
while(x%i==0)x/=i;
}
if(x>1)sum=sum/x*(x-1);
return sum;
}

map<int,int> M;

int Cal(int p) {
if(M.count(p))return M[p];
int phi=Phi(p);
return M[p]=Quick_Pow(2,Cal(phi)+phi,p);
}

int main() {
int t=Get_Int();
while(t--) {
int p=Get_Int();
printf("%d\n",Cal(p));
}
return 0;
}
姥爷们赏瓶冰阔落吧~