【洛谷P4139】上帝与集合的正确用法

小咪咪 2023-06-05 08:52 18阅读 0赞

### Description ###

给定$p$，求$2^\{2^\{2^\{2^\{2^\{...\}\}\}\}\}\\mod p$的值，多组询问。

### Solution ###

首先我们要知道欧拉定理的推论：

在b,p互质时，存在$a^b\\equiv a^\{b\\mod \\phi (p)\}\\pmod p$

在b,p不互质且b>φ(p)时，存在$a^b\\equiv a^\{b\\mod \\phi (p) + \\phi (p)\}\\pmod p$

根据第二条推论，这道题我们就可以转化一下：

假定$F=2^\{2^\{2^\{2^\{2^\{...\}\}\}\}\}$,那么$F=2^\{F\\mod \\phi(p)+\\phi(p)\}\\mod p$

这样，我们使用线性筛求出φ然后快速幂配合递归即可完成计算

### Code ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 ll n, p;
     5 const int maxn = 1e7 + 10;
     6 int v[maxn], ph[maxn], prime[maxn];
     7 int m;
     8 void phi() {
     9     for (register int i = 2; i <= maxn - 6; ++i) {
    10         if (!v[i]) {
    11             v[i] = i;
    12             prime[++m] = i;
    13             ph[i] = i - 1;
    14         }
    15         for (register int j = 1; j <= m; ++j) {
    16             if (prime[j] > v[i] || prime[j] > (maxn - 6) / i) break ;
    17             v[i * prime[j]] = prime[j];
    18             ph[i * prime[j]] = ph[i] * (i % prime[j] ? prime[j] - 1 : prime[j]);
    19         }
    20     }
    21 }
    22 ll qpow(ll a, ll n, ll p) {
    23     ll ret = 1; 
    24     while (n) {
    25         if (n & 1) ret = (ret * a) % p;
    26         a = a * a % p;
    27         n >>= 1;
    28     }        
    29     return ret;
    30 }
    31 ll calc(ll k) {
    32     if (k == 0) return 0;
    33     return qpow(2, calc(ph[k]) + ph[k], k);
    34 }
    35 int main() {
    36     phi();
    37     scanf("%lld", &n);
    38     while (n--) {
    39         scanf("%lld", &p);
    40         printf("%lld\n", calc(p));
    41     }
    42     return 0;
    43 }

AC Code

转载于:https://www.cnblogs.com/shl-blog/p/11342542.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/d5b247e7286a4cf393dd0a98811caa35.png