ACM基础数学

1.最大公约数，最小公倍数

int gcd(int x,int y)

{

    int z=y;

    while(x%y!=0)

    {

        z=x%y;

        x=y;

        y=z；

    }
    return z;
}


int lcm(int x,int y)

{

    return x*y/gcd(x,y);

}

2.快速幂

int qpow(int a,int b,int mod)//a^b
{
    int t=1;
    while(b)
    {
        if(b&1)
        {
            t=(t*a)%mod;
            b--;
        }
        a=(a*a)%mod;
        b>>=1;
    }
    return t;

>>矩阵快速幂很久以前收集的模板，亲测可用

struct Matrix
{
    int m[3][3];
};

Matrix Mul(Matrix a,Matrix b)

{

    Matrix c;

    memset(c.m,0,sizeof(c.m));

    for(int i=0;i<3;i++)

        for(int j=0;j<3;j++)

            for(int k=0;k<3;k++)

                c.m[i][j] += ((a.m[i][k]*b.m[k][j])%SMod + SMod)%SMod;



    return c;



}

Matrix fastm(Matrix a,int n) 

{
    Matrix res;

    memset(res.m,0,sizeof(res.m));

    res.m[0][0] = res.m[1][1] = res.m[2][2] = 1;

    while(n)

    {
        if(n&1)
            res = Mul(res,a);

        n>>=1;
        a = Mul(a,a);
    }
    return res;

}

Matrix MPow(Matrix a,int n)  //第二种写法,慎用,易RE

{

    if(n == 1)

        return a;

    Matrix res = fastm(a,n/2);

    res = Mul(res,res);
   if(n&1)

        res = Mul(res,a);

    return res;

}

另外一种

struct Matrix

{

    lll m[13][13];

    Matrix()

    {

        memset(m,0,sizeof(m));

        for(int i=1;i<=n+2;i++)

            m[i][i] = 1LL;

    }

};

Matrix Mul(Matrix a,Matrix b)

{

    Matrix res;

    int i,j,k;

    for(i=1;i<=n+2;i++)

    {

        for(j=1;j<=n+2;j++)

        {

            res.m[i][j] = 0;
            for(k=1;k<=n+2;k++)
                res.m[i][j] = (res.m[i][j]+(a.m[i][k]*b.m[k][j])%SMod + SMod)%SMod;
        }
    }
    return res;

}

Matrix fastm(Matrix a,int b)
{

    Matrix res;
    while(b)

    {

        if(b&1)
            res = Mul(res,a);
        a = Mul(a,a);

        b >>= 1;

    }

    return res;
}

对元素0较多的矩阵取快速幂时可在Mul函数中加一个小优化：

Matrix Mul(Matrix a,Matrix b)
{
    Matrix res;

    int i,j,k;

    memset(res.m,0,sizeof(res.m));

    for(k=1;k<=n+2;k++)

    {

        for(i=1;i<=n+2;i++)
        {
            if(a.m[i][k])

            {

                for(j=1;j<=n+2;j++)

                    res.m[i][j] = (res.m[i][j]+(a.m[i][k]*b.m[k][j])%SMod + SMod)%SMod;

            }
        }
    }

    return res;

}

3.排列组合

LL A(int n,int m)//n>=m

{
    int ans=1;
    if(n<m)return 0;

    while(m--)

    {

        ans*=n;
  n--;

    }

    return ans;

}
LL C(int n,int m)

{

    if(n<m)return 0;

    return A(n,m)/A(m,m);

}