情之所至,甘之如饴

数论是一门很棒的学科。在信息学竞赛中,数论算法一直是学习的重点、难点。它的代码实现较为简单,却不容易建立模型求解。因此,多加练习是解决这类题目的好方法。像大牛说的一样,“题做多了,考题都变成原题了”。

一句话题意

\[ 给定正整数p,求2^{2^{2^{2^...}}}(无限个2)mod\ p.\]

解法


首先来介绍一下欧拉函数及欧拉定理。

欧拉函数:设n是一个正整数,欧拉$ \varphi $函数$ \varphi(n) $定义为不超过n且与n互质(也称互素)的正整数的个数。

欧拉定理:设m是一个正整数,a是一个整数且$(a,m)=1 $(即:a, m互质),那么

接下来,我们引入扩展欧拉定理

这个定理不要求a和p互质,可以直接使用。

参考证明-来自知乎专栏

回到题目中,设$a=2,n=2^{2^{2^…}} $,由于有无穷个2,

所以有.

可以发现$ a^n \bmod p$和$a^n \bmod \varphi(p)$是一样的,所以我们可以递归求解。

边界条件:当$a^n \bmod p$为定值时结束。我们可以知道当$p=1$时这个式子必然等于0,可以结束。

这样时间复杂度是$ O(\log\ p) $的。这样加上快速幂就能求解了。

代码


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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;
#define R register
#define I inline
//宏定义
template<class T>void read(T &x) {
register int c = getchar(), f = 1; x = 0;
while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
//读入优化
inline ll qpow(ll x,ll y,ll p)
{
register ll ans=1;
while(y)
{
if(y&1) ans=ans*x%p;
x=x*x%p,y>>=1;
}
return ans;
}
inline ll phi(ll x)
{
register ll i,ans=x;
for(i=2;i*i<=x;i++)
{
if(x%i==0)
{
ans=ans/i*(i-1);
while(x%i==0) x/=i;
}
}
if(x!=1) ans=ans/x*(x-1);
return ans;
}
inline ll calc(ll p)
{
if(p==1) return 0;
register ll res=phi(p);
return qpow(2,calc(res)+res,p);
}
int main(){
register int t;
register ll p;
read(t);
for(register int i=1;i<=t;i++)
{
read(p);
printf("%lld\n",calc(p));
}
return 0;
}

参考资料


https://www.cnblogs.com/GXZlegend/p/6950483.html

https://blog.csdn.net/popoqqq/article/details/43951401/

https://zhuanlan.zhihu.com/p/24902174



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:726.4k