欧几里得算法

求两个正整数的最大公约数，时间复杂度O(logn)。

#define ll long long
ll gcd(ll a,ll b)//辗转相除法
{
    return b?gcd(b,a%b) : a;
}

扩展欧几里得算法

裴蜀定理：若 a,b 是整数,且 gcd(a,b)=d，那么对于任意的整数 x,y,ax+by 都一定是 d 的倍数，特别地，一定存在整数 x,y，使 ax+by=d 成立。

扩展欧几里得算法可以在 O(logn) 的时间复杂度内求出系数 x,y。

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

线性筛素数

可以在 O(n) 的时间复杂度内求出 1∼n之间的所有质数。

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}