关键词:欧拉定理 相关题目:上帝与集合的正确用法

exEuler

证明:三个重要的同余式——威尔逊定理、费马小定理、欧拉定理 + 求幂大法的证明

Description

... ...

一句话题意: 上帝与集合的正确用法

Input&Output

Input 接下来 TT 行,每行一个正整数 pp,代表你需要取模的值

Output TT 行,每行一个正整数,为答案对 pp 取模后的值

Sample Input

3
2
3
6

Sample Output

0
1
4

HINT

对于 100%100\% 的数据,

Source By PoPoQQQ

Solution

由欧拉定理,当 时, abab mod φ(p)+φ(p)(mod p)a^{b}\equiv a^{b~ mod~ \varphi(p) + \varphi(p)} (mod~p)。这里 b=222...b=2^{2^{2^{...}}} 显然大于 φ(p)\varphi(p) 。所以 222...222... mod φ(p)+φ(p)(mod p)2^{2^{2^{...}}} \equiv 2^{2^{2^{...}} ~ mod ~\varphi(p)+\varphi(p)} (mod~p) ,一直递归后,因为 φ(p)\varphi(p) 递减,最终为 11,而任意数 mod 10mod~1 \equiv 0 ,然后返回就好了。

这里有一道加强版的 Emma194-省选模拟赛.pdf 模拟赛第二题,这里 n=2n=2

以下代码为加强版题代码

AC代码

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
#include<cstdio>
typedef long long ll;
int T, p, n;
inline int phi(int x){
int res = x;
for(register int i=2; i*i<=x; ++i)
if(x%i==0){
res/=i, res*=i-1;
while(x%i==0) x/=i;
}
if(x^1) res /= x, res *= x-1;
return res;
} // 求φ(x)
inline int qmod(int a,int b,int p){
int res = 1;
while(b) {
if(b&1) res = (ll)res*a%p;
a = (ll)a*a%p;
b >>= 1;
}
return res;
}
inline int solve(int n, int p){
if(p==1) return 0;
return qmod(n, solve(n, phi(p))+phi(p), p);
}

int main(){
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &p);
printf("%d\n", solve(n, p));
}
}