一、整除

二元一次方程一般形式ax+by=c,有解的一般形式是GCD(X,N)|c。

x=x_0+b/(GCD(a,b)) t      y=y_0-a/(GCD(a,b)) t

二、同余

1、快速幂

一、整除

二元一次方程一般形式ax+by=c,有解的一般形式是GCD(X,N)|c。

x=x_0+b/(GCD(a,b)) t      y=y_0-a/(GCD(a,b)) t

二、同余

1、快速幂

int rep(int n,int m,int k){
    int ans=1;
    while(m){
        if(m&1)
            ans=ans*n%k;
        m>>=1;
        n=n*n%k;
    }
    return ans;
}

2、最大公约数

int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}

3、扩展欧几里得算法

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

4、解线性同余

int min_exgcd(int a,int b,int c,int &x,int &y){
    int d=exgcd(a,b,x,y);
    if(c%d==0){
        x*=c/d;
        int t=b/d;
        x=(x%t+t)%t;
        return t;
    }
}

5、逆元

int exgcd(int a,int b,int &d,int &x,int &y){
    if (b==0){
        d=a;
        x=1,y=0;
        return a;
    }
    int q=exgcd(b,a%b,d,y,x);
    y-=a/b*x;
    return q;
} 
int inverse(int a,int n){
    int d,x,y;
    exgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}

还有利用快速幂的http://www.bycore.net/?p=30

6、线性同余方程

int CRT(int a[],int m[],int n){
    int M=1,x,y;
    for(int i=0;i<n;i++)
        M*=m[i];
    int ans=0;
    for(int i=0;i<n;i++){
        int temp=M/m[i];
        exgcd(temp,m[i],x,y);
        ans+=a[i]*x*temp%M;
    }
}

7、斐波那契

8、卡特兰数

void caltl()
{
    for(int i = 2; i < 34; i ++)
        ctl[i] = ctl[i-1]*(4*i-2)/(i+1);
}

9、素数(欧拉线性筛法)

for(p=2;p*p<=n;next(x))
    for((q=p;p*p<=n;next(q)))
        for(m=p*q;m<=n;m=p*m)
            remove(m);

发表评论

电子邮件地址不会被公开。 必填项已用*标注