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