学了一下扩展欧拉定理,不会证,记了个结论,笔记的话,随便去网上搜一搜吧.

-bzoj3884:上帝与集合的正确用法

无脑板子题额

#include 
      
       #include 
       
        #include 
        
         typedef long long LL;inline int Pow(int x,int y,int P){    int ret=1;    while(y){        if(y&1)ret=(LL)ret*x%P;        x=(LL)x*x%P,y>>=1;    }    return ret;}inline int Phi(int x){    if(x==1)return 1;    int i,ret=x;    for(i=2;i*i<=x;++i)        if(x%i==0){            ret=ret/i*(i-1);            while(x%i==0)x/=i;        }    if(x!=1)ret=ret/x*(x-1);    return ret;}inline int Power(int P){    if(P==1)return 0;    int phi=Phi(P);    return Pow(2,Power(phi)+phi,P);}int main(){    int T,P;    scanf("%d",&T);    while(T--){        scanf("%d",&P);        printf("%d\n",Power(P));    }    return 0;}
        
       
      

-bzoj4869:[Shoi2017]相逢是问候

见

这道题的小细节还是比较坑的啊,比如:1.多加一个1;2.判断上一层和上一层模数的大小关系.(网上的人大概都是判0或者试乘,我写的是试乘,因为我不会证明判0的正确性,而且也看不懂除了试乘以外的方法)(我的试乘比较蠢,但是他的正确性我应该是证出来了(不过证明过程写在纸上,懒得往上搬了))

#include 
      
       #include 
       
        #include 
        
         #include 
         
          typedef long long LL;const int A=50;const int N=50010;const int F=1<<15;const int oo=100000000;int n,m,k,P,cmp,hp,phi[A],a[N],mi1[A][F+10],mi2[A][F+10];inline int Pow(int x,int y,int P,int cur){    int ret=(LL)mi1[cur][y&(F-1)]*mi2[cur][y>>15]%P;    return ret;}inline int Pow_(int x,int y,int P,int cur){    if(y>=cmp)return Pow(x,y,P,cur);    LL ret=1;    int i;    for(i=1;i<=y;++i){        ret*=x;        if(ret>=P)return Pow(x,y,P,cur);    }    return ret+oo;}inline int Phi(int x){  if(x==1)return 1;  int i,ret=x;  for(i=2;i*i<=x;++i)    if(x%i==0){      ret=ret/i*(i-1);      while(x%i==0)x/=i;    }    if(x!=1)ret=ret/x*(x-1);  return ret;}inline int Power(int rest,int aim,int P,int cur){    if(!rest)return aim
          
           sum+ch[1]->sum)%P;        hp=ch[0]->hp+ch[1]->hp;    }}*root,node[N<<2];int sz;#define newnode (node+(sz++))#define mid ((l+r)>>1)inline void build(Segment_Tree *&p,int l,int r){    p=newnode;    if(l==r){        p->hp=hp;        p->sum=a[l];        return;    }    build(p->ch[0],l,mid);    build(p->ch[1],mid+1,r);    p->pushup();}inline void dfs(Segment_Tree *p,int l,int r){    if(!p->hp)return;    if(l==r){        --p->hp;        p->sum=k==1?1:Power(hp-p->hp,a[l],P,0);        if(p->sum>=oo)p->sum-=oo;        return;    }    dfs(p->ch[0],l,mid);    dfs(p->ch[1],mid+1,r);    p->pushup();}inline void update(Segment_Tree *p,int l,int r,int z,int y){    if(z<=l&&r<=y){        dfs(p,l,r);        return;    }    if(z<=mid)update(p->ch[0],l,mid,z,y);    if(mid
           
            ch[1],mid+1,r,z,y); p->pushup();}inline int query(Segment_Tree *p,int l,int r,int z,int y){ if(z<=l&&r<=y)return p->sum; int ret=0; if(z<=mid)ret+=query(p->ch[0],l,mid,z,y); if(mid
            
             ch[1],mid+1,r,z,y); return ret%P;}inline void Init(){ scanf("%d%d%d%d",&n,&m,&P,&k); int cur=P,step=-1,i,j; while(true){ phi[++step]=cur; if(cur==1)break; cur=Phi(cur); } hp=step; phi[++hp]=1; for(i=0;i<=hp;++i){ mi1[i][0]=1%phi[i]; for(j=1;j