(luogu4139)上帝与集合的正确用法 发表于 2021-07-11 | 分类于 solution , 数论 原题链接 思路:由扩展欧拉定理, 有: 上面的$2^{2\cdots} \mod \varphi(p)$可以递归求解, 当$\varphi(p)$减小到1即可回溯. 至于$\varphi(p)$, 用线性筛预处理即可. 代码:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include <cstdio>#include <vector>using namespace std;const int Mp(10000050);int phi[Mp];vector<int> prm;void euler() { //线性筛 phi[1] = 0; for(int i(2);i<Mp;++i) { if(!phi[i]) { phi[i] = i-1; prm.push_back(i); } for(int j(0);j<prm.size() && 1ll*i*prm[j]<Mp;++j) { if(i%prm[j]==0) { phi[i*prm[j]] = phi[i]*prm[j]; break; } else { phi[i*prm[j]] = phi[i]*(prm[j]-1); } } }}int ksm(int a,int b,int p) { //快速幂 int ret(1),tmp(a%p); for(int i(0);(1<<i)<=b;++i) { if(b&(1<<i)) { ret = 1ll*ret*tmp%p; } tmp = 1ll*tmp*tmp%p; } return ret;}int ans(int p) { //递归求解 if(p<=1) { //边界条件 return 0; } else { return ksm(2,ans(phi[p])+phi[p],p); }}int main() { euler(); int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); printf("%d\n",ans(n)); } return 0;}