线性筛

线性筛素数

#include
     
      using namespace std;const int N=10000000+5,inf=0x3f3f3f3f;int n,m;int prime[N],v[N],num_prime=0;int main(){        scanf("%d%d",&n,&m);    memset(prime,0,sizeof(prime));    memset(v,0,sizeof(v));    for(int i=2;i<=n;++i){        if(!v[i]) v[i]=i,prime[++num_prime]=i;        for(int j=1;j<=num_prime&&i*prime[j]<=n;++j){            v[i*prime[j]]=prime[j];            if(!(i%prime[j])) break;        }    }    for(int i=1,x;i<=m;++i){        scanf("%d",&x);        if(v[x]==x) puts("Yes");        else puts("No");    }    return 0;}
     

扩欧

求关于x的同余方程ax≡1(modb)的最小正整数解

 

#include
     
      using namespace std;#define ll long longvoid exgcd(ll a,ll b,ll &x,ll &y){    if(!b) {x=1,y=0;return;}    exgcd(b,a%b,x,y);    ll t=x;x=y,y=t-(a/b)*y; }ll A,B,x,y;int main(){        scanf("%lld%lld",&A,&B);     exgcd(A,B,x,y);    printf("%lld",(x%B+B)%B);    return 0;}
     

 

逆元

线性逆元筛

#include
     
      using namespace std;#define ll long longconst int N=20000528+55;int n,p;ll inv[N];int main(){    scanf("%d%d",&n,&p);    inv[1]=1;puts("1");    for(int i=2;i<=n;++i)    inv[i]=(ll)inv[p%i]*(p-p/i)%p,printf("%lld\n",inv[i]);    return 0;}
     

logn求逆元 费马小定理 扩展欧几里德 

中国剩余定理

中国剩余定理

#include
     
      using namespace std;#define ll long longint n,a[15],m[15],M;template
      
       void rd(t &x){    x=0;int w=0;char ch=0;    while(!isdigit(ch)) w|=ch=='-',ch=getchar();    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();    x=w?-x:x;}void exgcd(ll a,ll b,ll &x,ll &y){
   //扩展欧几里德    if(!b) {x=1,y=0;return;}    exgcd(b,a%b,x,y);    ll t=x;x=y,y=t-a/b*y;}ll china(int n,int *a,int *m){    ll ans=0,M=1,x,y;    for(int i=1;i<=n;++i) M*=m[i];    for(int i=1;i<=n;++i){        ll mi=M/m[i];        exgcd(mi,m[i],x,y);        x=(x%m[i]+m[i])%m[i];        ans=(ans+a[i]*mi*x)%M;    }    return (ans+M)%M; }int main(){    rd(n);    for(int i=1;i<=n;++i) rd(a[i]);    for(int i=1;i<=n;++i) rd(m[i]);    printf("%lld",china(n,a,m));    return 0;}
      
     

扩展中国剩余定理

暂时粘上以前的...

#include
     
      using namespace std;const int N=1e5+5;#define ll long longll n,ai[N],bi[N];template
      
       void rd(t &x){    x=0;int w=0;char ch=0;    while(!isdigit(ch)) w|=ch=='-',ch=getchar();    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();    x=w?-x:x;}ll exgcd(ll a,ll b,ll &x,ll &y){    if(!b) {x=1,y=0;return a;}    ll gcd=exgcd(b,a%b,x,y);    ll t=x;x=y,y=t-a/b*y;    return gcd;}ll mul(ll a,ll b,ll mod){    ll ans=0;    while(b)    {        if(b&1) ans=(ans+a)%mod;        a=(a+a)%mod,b>>=1;    }    return ans;}ll excrt(){    ll x,y;    ll M=bi[1],ans=ai[1];//第一个方程的解    for(int i=2;i<=n;i++)    {        ll a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;        ll gcd=exgcd(a,b,x,y),bg=b/gcd;        //求方程 t*M mod bi =ai-x 的解t        if(c%gcd) return -1;        x=mul(x,c/gcd,bg);        ans+=x*M,M*=bg,ans=(ans%M+M)%M;     }     return (ans%M+M)%M;}int main(){    rd(n);    for(int i=1;i<=n;i++) rd(bi[i]),rd(ai[i]);    printf("%lld",excrt());    return 0;}