数论基础

1、欧几里德算法

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b , a%b);
}

int lcm(int a, int b)
{
    return a/gcd(a,b)*b;//防止溢出

}

2、Eratosthenes筛法

int m = sqrt(int n+0.5);
memset(vis, 0, sizeof(vis));
for(int i = 2; i <= m; i++)
{
    if(!vis[i])
    for(int j = i*i; j <= n; j += i)
    {
        vis[j] = 1;
    }
}

3、扩展欧几里德算法

4、同余与模算术

1)同余定理

//(a+b)%n=(a%n+b%n)%n

//(a-b)%n=(a%n-b%n+n)%n

//a*b%=(a%n)*(b%n)%n;

int mul_mod(int a, int b, int n)
{
    a %= n;
    b %= n;
    return (int)((long long)a * b % n);
}

2）大数取模

scanf("%s%d",n, &m);
int len = strlen(n);
int ans = 0;
for(int i = 0; i < len; i++)
{
    ans=(int)((long long)ans*10 + n[i] - '0') % m);
}
printf("%d
",ans);

3）幂取模

int pow_mod(LL a,LL n,int m)
{
    if(n==0) return 1;
    LL x=pow_mod(a,n/2,m);
    LL ans=x*x%m;
    ans=ans%m;
    if(n%2==1) ans=ans*a%m;
    return (int)ans;
}

4）矩阵快速幂

struct Matrix
{
    int mp[N][N];
};

Matrix Mul(Matrix a,Matrix b)
{
    int i,j,k;
    Matrix c;
    for(i=0; i<N; i++)
        for(j=0; j<N; j++)
        {
            c.mp[i][j]=0;
            for(k=0; k<N; k++)
            {
                c.mp[i][j]+=a.mp[i][k]*b.mp[k][j];
                c.mp[i][j]%=M;
            }
        }
    return c;
}

/*
Matrix Pow(Matrix t,int n)
{
    if(n==1) return t;
    Matrix c=Pow(t,n/2);
    if(n&1)
        return Mul(Mul(c,c),t);
    else
        return Mul(c,c);
}
*/

Matrix Pow(Matrix a,int n)
{
    Matrix c;
    for(i=0;i<N;i++)
        c.mp[i][i]=1;
    while(n)
    {
        if(n&1) c=Mul(c,a);
        a=Mul(a,a);
        n/=2;
    }
    return c;
}