上帝与集合的正确做法 拓展欧拉定理 欧拉函数性质
题意
求
[2^{2^{2^{2...}}} mod p
]
[p leq 10^7
]
分析
拓展欧拉定理
[a^b =
egin{cases}
a^{b mod phi(p)},gcd(a,p) = 1\
a^b , gcd(a,p)
eq 1 and bleq phi(p)\
a^{b mod phi(p) + phi(p)}, gcd(a,p)
eq1and bgeq phi(p)
end{cases}
]
欧拉函数的一种计算式：
[phi(n) = n prod_{i=1}(1-frac{1}{p_i})
]
可以推出
- (n>2)时，(2|phi(n)) 与(n)互质的数总是成对出现
- (n)为奇数时，(phi(2n) = phi(n))
可以对上式变换
[2^{2^{2^{2...}}} mod p = 2^{P mod phi(p) + phi(p)} mod p\
P mod phi(p) = 2^{P' mod phi(phi(p)) + phi(phi(p))} mod phi(p)\
...
]
我们发现求这个的过程相当于对(p)迭代(phi(x))函数
而容易发现**(p -> phi(p)) 如果(2|p)那么大小至少减小一半(计算式) **
如果(p)是奇数，那么(phi(p) = phi(2p)) ,(2 | phi(2p)) 即一定会成为偶数
因此经过(2log)次迭代就会变为1
于是直接暴力迭代就会快速迭代完毕
代码
#include<bits/stdc++.h>
#define pii pair<ll,ll>
#define fi first
#define se second
using namespace std;
typedef long long ll;
inline ll rd(){
ll x;
scanf("%lld",&x);
return x;
}
const int MOD = 1e9 + 7;
inline int mul(int a,int b){
int res = (ll)a * b % MOD;
if(res < 0) res += MOD;
return res;
}
inline void add(int &a,int b){
a += b;
if(a >= MOD) a -= MOD;
}
inline void sub(int &a,int b){
a -= b;
if(a < 0) a += MOD;
}
const int maxn = 3e6 + 5;
inline int ksm(int a,int b = MOD - 2,int m = MOD){
int ans = 1;
int base = a;
while(b){
if(b & 1) ans = (ll)ans * base % m;
base = (ll)base * base % m;
b >>= 1;
}
return ans;
}
inline int get_phi(int n) {
int m = int(sqrt(n + 0.5));
int ans = n;
for (int i = 2; i <= m; i++) {
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
int get(int x){
if(x < 3) return 0;
int n = get_phi(x);
return ksm(2,n + get(n),x);
}
int main(){
int T = rd();
while(T--){
int x = rd();
printf("%d
",get(x));
}
}