1.欧几里得算法

可以通过欧几里得算法求出最大公因子。

int gcd(int x, int y) //欧几里得算法 
{ 
    return y==0 ?  x : gcd(y, x%y);
}

2.扩展欧几里得

可以通过扩展欧几里得求出\(ax+by=d\)不定方程的一组整数解。（a, b, d为正整数）

void exgcd(int a, int b, int& x, int& y) //扩展欧几里得 
{
    if(!b)
    {
        x=1; y=0;
        return ;
    }
    exgcd(b, a%b, y, x);
    y-=(a/b)*x; 
}

3.快速幂

可以通过快速幂在\(O(logn)\)的复杂度下求出\(x^y\%p\)

LL ksm(LL x, LL y, int p) //快速幂 
{
    LL ans=1;
    while(y)
    {
        if(y&1) ans=(ans*x)%p;
        y>>=1; x=(x*x)%p;
    }
    return ans%p;
}

4.质因数分解

可以求出一个整数的所有质因数（没有去重）

void factor(int num) //质因数分解 
{
    int fac[MAXN],cnt;
    while(num!=1)
        for(int i=2; i<=num; i++) if(num%i==0)
        {
            fac[++cnt]=i;
            num/=i; i=1;
        }
    for(int i=1; i<=cnt; i++) printf("%d ",fac[i]);
}

5.费马小定理求组合数

可以求$C(n, m)%p $ 其中需要\(n,m\)较小，较大时要用卢卡斯定理优化。

LL combine(LL x, LL y)   //费马小定理求组合数 
{  
    LL up=1, down=1;  
    for(LL i=0; i<y; i++)
    {  
        up=up*(x-i)%p;  
        down=down*(i+1)%p;  
    }  
    return up*ksm(down, p-2, p)%p;  //可以直接使用上文给出的ksm()
}

6.卢卡斯定理求组合数

同样可以求$C(n, m)%p $ 其中 $p<=10^5 $ $ n, m<=10^{18}$。

LL lucas(LL x, LL y) //卢卡斯定理求组合数 
{  
    if(!y) return 1;  
    return combine(x%p, y%p)*lucas(x/p, y/p)%p;  //可以直接使用上文给出的combine()
}

7.中国剩余定理

可以求解一元线性同余方程组。

LL china(int n, int *a, int *m) //中国剩余定理 
{
    LL p=1, ret=0, x, y;
    for(int i=1; i<=n; i ++) p*=m[i];
    for(int i=1; i<=n; i ++)
    {
        LL w=p/m[i];
        exgcd(m[i], w, x, y); //可以直接使用上文的exgcd()
        ret=(ret+w*y*a[i])%p;
    }
   return (ret+p)%p;
}

8.线性素数筛

可以求出1-num内所有的素数。

void prime(int num) //素数筛 
{
    int cnt=0, check[MAXN], pri[MAXN];
    sizeof(check, true, sizeof(check));
    check[1]=false;
    for(int i=2; i<=num; i++)
    {
        if(check[i]) pri[++cnt]=i;
        for(int j=0; j<cnt && i*pri[j]<=num; j++)
        {
            check[i*pri[j]]=false;
            if(i%pri[j]==0) break;
        }
    }
}

9.欧拉函数筛

可以求出1-num内的欧拉函数。

void euler(int num) //欧拉函数筛 
{     
    int cnt=0, check[MAXN], eul[MAXN], pri[MAXN];
    sizeof(check, true, sizeof(check));  
    check[1]=false; eul[1]=1;  
    for(int i=2; i<=num; i++)
    {
        if(check[i])
        {
            pri[++cnt]=i;
            eul[i]=i-1;
        }
        for(int j=0; j<cnt && i*pri[j]<=num; j++)
        {
            check[i*pri[j]]=false;
            if(i%pri[j]==0)
            {
                eul[i*pri[j]]=eul[i]*pri[j];
                break;
            }
            eul[i*pri[j]]=eul[i]*(pri[j]-1);
        }
    }      
}

10.莫比乌斯函数筛

可以求出1-num内的莫比乌斯函数

void mobius(int num) //莫比乌斯函数筛 
{
    int cnt=0, check[MAXN], mob[MAXN], pri[MAXN];
    sizeof(check, true, sizeof(check));
    check[1]=false; mob[1]=1;  
    for(int i=2; i<=num; i++)
    {
        if(check[i])
        {
            pri[++cnt]=i;
            mob[i]=-1;
        }
        for(int j=0; j<cnt && i*pri[j]<=num; j++)
        {
            check[i*pri[j]]=false;
            if(i%pri[j]==0)
            {
                mob[i*pri[j]]=0;
                break;
            }
            mob[i*pri[j]]=-mob[i];
        }
    }  
}