剛開始我想的是歐拉降冪，可是覺得復(fù)雜度還是挺高的就去找了一下題解。

思路大方向沒有問題，仍然是使用歐拉函數(shù)降低指數(shù)然后遞歸處理。但是不是簡單的使用歐拉降冪而是應(yīng)該對模數(shù)p稍微處理一下。因?yàn)榈讛?shù)已經(jīng)確定為2，所以我們可以將p寫成p=2^k*q，q為奇數(shù)的形式，則

2^{2的無窮次方}%p=2^k(2^{2的無窮次方-k}%q)

這樣可以直接對新的指數(shù)直接模q的歐拉函數(shù)值進(jìn)行處理，因?yàn)槊看蝢為奇數(shù)，q的歐拉函數(shù)值一定為偶數(shù)（他的因子一定是奇素?cái)?shù)，奇素?cái)?shù)的歐拉函數(shù)值一定是偶數(shù)），所以每次至少將p變?yōu)樵瓉淼囊话?#xff0c;所以復(fù)雜度比較低。因?yàn)橛玫降臍W拉函數(shù)值不是很多，所以直接求單點(diǎn)的歐拉函數(shù)值即可。

需要注意的是指數(shù)-k模歐拉函數(shù)值時應(yīng)該保證指數(shù)大于0

AC代碼

#include<cstdio> #include<cstring> #include<algorithm> #include<climits> #include<cmath> #include<cstdlib> #include<ctime> #include<map> #include<queue> #include<set> #include<vector>using namespace std;typedef long long ll; const int MAXN=1e5+5;ll p;ll quick_pow(ll a,ll b,ll p) {a%=p; ll ret=1;while(b){if(b&1) ret=ret*a%p;a=a*a%p; b>>=1;}return ret; }ll quick_pow(ll a,ll b) {ll ret=1;while(b){if(b&1) ret*=a;a*=a; b>>=1;}return ret; }ll phi(int x) {ll ret=x;for(int i=2;i*i<=x;i++){if(x%i==0){ret=ret-ret/i;while(x%i==0) x/=i;}if(x==1) break;}if(x>1) ret=ret-ret/x;return ret; }ll deal(ll p) {ll k=0;while(~p&1) k++,p>>=1;if(p==1) return 0;ll phip=phi(p);return quick_pow(2,(deal(phip)-k%phip+phip)%phip,p)<<k; }int main() {int T;scanf("%d",&T);while(T--){scanf("%lld",&p);printf("%lld\n",deal(p));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ3884上帝与集合的正确用法-欧拉函数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。