资讯详情

既然是EX，那cost是多少

扩展欧几里得

int exgcd(int a,int b,int &x,int &y)
{if(b==0){x=1;y=0;return a;}int ret=exgcd(b,a%b,x,y);int t=x;x=y;y=t-a/b*y;return ret;
}

扩展欧拉定理

扩展欧拉定理:

· 当\(a,m\)互质:\(a^b\equiv a^{b\ mod\ \varphi(m)}(mod\ m)\)

· 当\(a,m\)不互质且\(b<\varphi(m)\)同余于它本身

· 当他两个不互质且\(b>=\varphi(m)\):\(a^b\equiv a^{b\ mod\ \varphi(m)+\varphi(m)}(mod\ m)\)
顺便提一嘴欧拉定理：\(a^{\varphi(m)}\equiv1(mod\ m)\)

扩展中国剩余定理

int gsc(int x,int y,int mo)
{int ret=0;while(y){if(y&1) (ret+=x)%=mo;y>>=1;x=(x+x)%mo;}return ret;//龟速乘，防爆long long
}

for(int i=1;i<=n;i++) cin>>mod[i]>>yu[i];int ans=yu[1],M=mod[1],t=0,y=0;for(int i=2;i<=n;i++){int rig=((yu[i]-ans)%mod[i]+mod[i])%mod[i];int gcd=exgcd(M,mod[i],t,y);if(rig%gcd!=0){ans=-1;break;}t=gsc(t,rig/gcd,mod[i]);ans+=M*t;M=mod[i]/gcd*M;ans=(ans%M+M)%M;}cout<<ans<<'\n';	

扩展lucas

void fj(int x)
{for(int i=2;i*i<=x;i++){if(x%i==0){cc[++tot]={i,1};while(x%i==0){cc[tot].val*=i;x/=i;}}}if(x>1) cc[++tot]={x,x};
}

int fat(int nn,int p,int k)
{if(!nn) return 1;int ret=1;for(int i=2;i<k;i++){if(i%p) ret=ret*i%k;}ret=ksm(ret,nn/k,k);for(int i=2;i<=nn%k;i++){if(i%p) ret=ret*i%k;}return ret*fat(nn/p,p,k)%k;
}

int inv(int a,int b)
{int x=0,y=0;exgcd(a,b,x,y);return (x+b)%b;
}
int C(int nn,int mm,int p,int k)
{if(nn<mm) return 0;int a=fat(nn,p,k),b=fat(mm,p,k),c=fat(nn-mm,p,k);int cnt=0;for(int i=p;i<=nn;i*=p) cnt+=nn/i;for(int i=p;i<=mm;i*=p) cnt-=mm/i;for(int i=p;i<=nn-mm;i*=p) cnt-=(nn-mm)/i;return a*inv(b,k)%k*inv(c,k)%k*ksm(p,cnt,k)%k;
}

int exlucas()
{fj(P);int ans=0;for(int i=1;i<=tot;i++){yu[i]=1;int op=nx;for(int j=1;j<=mx;j++){(yu[i]*=C(op,w[j],cc[i].pos,cc[i].val))%=cc[i].val;op-=w[j];}}for(int i=1;i<=tot;i++){int mi=P/cc[i].val;ans+=yu[i]%P*(mi*inv(mi,cc[i].val)%P)%P;}ans=(ans+P)%P;return ans;
}