BZOJ3884: 上帝与集合的正确用法 数论

首先我们知道欧拉定理:

\[a^{\phi(p)}=1(mod~p)((a,p)=1)\]

那么看起来这道题有点能做了.

可惜如果\(p\)是偶数又怎么办?

我们有\(cx%cy=c(x%y)\)这条神奇的性质.也很容易证明.

这样,我们就可以将问题递归处理了.

对于\(\phi\)函数的不断迭代是\(log\)级别的,然后我们每次\(O(\sqrt{n}logn)\)求\(\phi\).因此时间复杂度为\(O(\sqrt{n}logn)\).

还有另外一种不用讨论的方法:

有公式:\(a^x=a^{x\%\phi(p)+\phi(p)}(mod~p)(x>=\phi(p))\)

这样就能更加自然地递归下去了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
inline int getphi(int x){
    int re=x,t=x;
    for(int i=2;i*i<=x;++i){
        if(t%i==0){
            re=(LL)re*(i-1)/i;
            while(t%i==0)t/=i;
        }
    }if(t!=1)re=(LL)re*(t-1)/t;
    return re;
}
 
inline int ksm(int x,int y,int p){
    int re=1,t=x;for(;y;y>>=1,t=(LL)t*t%p)if(y&1)re=(LL)re*t%p;return re;
}
inline int calc(int p){
    if(p==1)return 0;
    else{
        int phi=getphi(p),re=calc(phi);
        return ksm(2,re+phi,p);
    }
}
 
int main(){
    int T,p;scanf("%d",&T);
    while(T--){
        scanf("%d",&p);
        printf("%d\n",calc(p));
    }
    return 0;
}