数论

懂基础的就行，这玩意可太抽象了。

1.最大公约数

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

2.最小公倍数

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

int lcm(int a,int b)
{
    return a * b / gcd(a, b);
}

3.快速幂

int qmi(int a, int b, int p)
{
    int res = 1;
    while(b)
    {
        if(b & 1)
        {
            res = (ll)res * a % p;
        }
        b >>= 1;
        a = (ll)a * a % P;
    }
    return res;
}

4.快速幂求逆元(这个地方研究了好久，一直搞不懂它的本质，就当做求倒数吧)

int qmi(int a, int b, int p)
{
    int res = 1;
    while(b)
    {
        if(b & 1)
        {
            res = (ll)res * a % p;
        }
        b >>= 1;
        a = (ll)a * a % P;
    }
    return res;
}

int res = qmi(a, p-2, p);//res就为逆元;

5.试除法判定质数

bool isprime(int x)
{
    if(x < 2)return false;

    for(int i = 2; i <= x / i; i ++ ) //"="不要忘记
    {
        if(x % i == 0)
        {
            return false;
        }
    }

    return true;
}

6.线性筛质数(1 - 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;
        }
    }
}

7.组合计数

(一)(预处理，时间复杂度较高)

void init()
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j==0)
            {
                c[i][j] = 1;
            }
            else
            {
                c[i][j] = (c[i-1][j]+c[i-1][j-1]) % mod;
            }
        }
    }
}

(二)(预处理 + 快速幂求逆元(组合数公式))

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int main()
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++ )
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

(三)Lucas定理(看看就行了，我感觉前两个的时间复杂度够用了)

8.欧拉公式(求1 - n中与n互质的数的个数)(记住公式就好)

int main()
{
    int n;
    cin >> n;

    while(n -- )
    {
        int x;
        cin >> x;

        int res = x;
        for(int i = 2; i <= x / i; i ++ )
        {
            if(x % i == 0)
            {
                res = res * (i - 1) / i;
            }
            while(x % i == 0)
            {
                x /= i;
            }
        }
        if(x > 1)
        {
            res = res * (x - 1) / x;
        }

        cout << res << endl;
    }

    return 0;
}