[BZOJ 3884] 上帝与集合的正确用法【欧拉定理/初等数论】

[Description]求值

[Solution] 不要被无限个2吓到了，这一题有一些有趣的性质可以发掘的。 这里介绍两个解法。

· Solution 1

我们温习一下欧拉定理：

和它的推广：

我们发现，这题的n,p并不一定互素啊，怎么办呢？我们可以让他们强行互素。 利用公式：

我们把原题中的p分为2^k+y 所以原式化为

此时y是奇数，和指数互质了！然后就可以愉快地使用欧拉定理–原式化为

我们发现中间的指数一部分又与原问题相似，于是想到可以递归求解。 那边界是什么呢？我们发现，，phi(y)会不断缩小，而且每次至少会除去一个2，所以递归的深度最多为log2(p),当y=1时，返回0即可。

需要事先筛好phi值或者直接需要的时候根号时间计算求解。

复杂度O(p+log2(p))–线性筛/O(log2(p)*sqrt(p))–直接计算。 实践过程中第二种方法远远快于第一种。

· Solution 2

还是根据公式

设答案为f(p),有

同样递归求解即可，复杂度同第一个解。

[Code]

给出两种解法的代码，第一种用的线性筛，第二种直接求解。

· Code 1

#include<cstdio>typedef long long ll;const int maxn=10000001;int phi[maxn]={0,1};void MakePhiList(){for(int i=2;i<maxn;i++) if(!phi[i])for(int j=i;j<maxn;j+=i){if(!phi[j]) phi[j]=j;phi[j]=phi[j]/i*(i-1);}}ll pow(ll a,int n,int p){ll ans=1;while(n) {if(n&1) ans=ans*a%p;a=a*a%p; n>>=1;}return ans;}ll f(int x){if(x==1) return 0;int k=0; while(!(x%2)) x/=2,k++;return pow(2,(f(phi[x])%phi[x]-k%phi[x]+phi[x])%phi[x]+phi[x],x)<<k;}int main(){MakePhiList();int kase; scanf(“%d”,&kase);while(kase–){int x; scanf(“%d”,&x);printf(“%lld\n”,f(x));}return 0;}

· Code 2

#include<cmath>#include<cstdio>typedef long long ll;int Phi(int x){int ans=x;for(int i=2,lim=sqrt(x)+1;i<lim;i++) if(!(x%i)){ans-=ans/i;while(!(x%i)) x/=i;}return x>1?ans-ans/x:ans;}ll pow(ll a,ll n,ll p){ll ans=1;while(n){if(n&1) ans=ans*a%p;a=a*a%p; n>>=1;}return ans;}ll f(int x){if(x==1) return 0;int phi=Phi(x);return pow(2,f(phi)+phi,x);}int main(){int kase; scanf(“%d”,&kase);while(kase–){int x; scanf(“%d”,&x);printf(“%lld\n”,f(x));}return 0;}

也就越容易失败，还不如怀揣一颗平常心，