學習借鑒了skywalkert大佬的題解?Orz

首先題目需要用到歐拉函數的一個性質

$\forall x\geq \phi(p)$

$a^x\equiv a^{x \; mod \; \phi(p) + \phi(p)}(mod\;p)$

設$f(p) = 2^{2^{2^{...}}}mod \; p$

$f(p)=2^{(2^{2^{...}} mod \; \phi(p)) + \phi(p)}mod \; p \\=2^{f(\phi(p)) + \phi(p)} mod \; p$

關于f(p)的遞推式知道了，只要dfs就可以了。

時間復雜度$O(\sqrt{p}logp)$

map的作用就是記錄取模x的時候的值

#include <cstdio> #include <map> using namespace std;map<int,int>vis;int pow(int x,int k,int p){int ans = 1;while(k){if(k&1) ans=(long long )ans*x%p;x = (long long)x * x % p;k>>=1;}return ans; }int phi(int x){int ans = x;for(int i=2;i*i<=x;i++){if(x%i==0){ans -= ans/i;while(x%i==0) x/=i;}}if(x>1) ans -= ans/x;return ans; }int dfs(int x){if(vis.count(x)) return vis[x];int p = phi(x);return vis[x] = pow(2,dfs(p)+p,x); }int main(){int t,n;scanf("%d",&t);vis[1]=0;while(t--){scanf("%d",&n);printf("%d\n",dfs(n));}return 0; }

?

轉載于:https://www.cnblogs.com/OIerLYF/p/7504243.html

總結

以上是生活随笔為你收集整理的BZOJ 3884 上帝与集合的正确用法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。