1.数论

1.1质数

1.1.1试除法判断是否为质数 O($\sqrt{n}$)

bool is_prime(int x)
{
    if(x < 2) return false;
    for(int i = 2; i <= x / i ; i ++)
        if(x % i == 0)
            return false;

    return true;
}

p.s

1.循环的终止条件设置为 i <= x / i 而非 i * i <= x 是为了防止两个int相乘导致溢出

1.1.2普通筛法 O(nlogn)

void get_primes(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i]) primes[cnt ++] = i;

        for(int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

1.1.3埃氏筛法 O(nloglogn)

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

1.1.4线性筛法 O(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] * i <= n; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

void get_primes(){
    //外层从2~n迭代，因为这毕竟算的是1~n中质数的个数，而不是某个数是不是质数的判定
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){//primes[j]<=n/i:变形一下得到——primes[j]*i<=n,把大于n的合数都筛了就
        //没啥意义了
            st[primes[j]*i]=true;//用最小质因子去筛合数

            //1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j]<i的
            //最小质因子,所以primes[j]*i的最小质因子就是primes[j];
            //2)当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是
            //prime[j]，之后接着用st[primes[j+1]*i]=true去筛合数时，就不是用最小质因子去更新了,因为i有最小
            //质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子，此时就应该
            //退出循环，避免之后重复进行筛选。
            if(i%primes[j]==0) break;
        }
    }
}

作者：orzorz
链接：https://www.acwing.com/solution/content/7950/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1.1.5试除法分解质因数 O($\sqrt{n}$)

void divide(int x)
{
    for(int i = 2; i <= x / i ; i ++)
        if(x % i == 0)
        {
            int s = 0;
            while(x % i == 0) x /= i, s ++;
            cout << i << ' ' << s << endl;
        }
    if(x > 1) cout << x << ' ' << 1 << endl;
    puts("");
}

ps

1.不要忘记判断最后剩下的x是不是一个大的质因子

1.2约数

1.2.0前置知识

a.算术基本定理：

对于任意正整数N = $P1^{a1}\*P2^{a2}\*\cdots*Pn^{an}$

这里P1 < P2 < ··· < Pn均为质数，其中指数ai是正整数

b.求约数的个数：

S = (a1 + 1) * (a2 + 1) * ··· *(an + 1)

c.求所有约数的和（容斥原理）

S = $(P1^0+P1^1+\cdots+P1^{a1})\*(P2^0+P2^1+\cdots+P2^{a2})\*\cdots*(Pn^0+Pn^1+\cdots+Pn^{an})$

1.2.1试除法求约数 O($\sqrt{n}$)

void divisors(int n)
{
    vector<int> v;
    for(int i = 1; i <= n / i ; i ++)
        if(n % i == 0)
        {
            v.push_back(i);
            if(i != n / i) v.push_back(n / i);
        }

    sort(v.begin(), v.end());

    for(int i = 0; i < v.size(); i ++)
        printf("%d ", v[i]);
}

1.2.2约数个数

LL get(int x)
{
    unordered_map<int, int> primes;

    for(int i = 2; i <= x / i ; i ++)
        while(x % i == 0)
        {
            x /= i;
            primes[i] ++;
        }

    if(x > 1) primes[x] ++;

    LL res = 1;
    for(auto p : primes) res = res * (p.second + 1) % mod;

    return res;
}

1.2.3约数之和

LL get(int x)
{
    unordered_map<int, int> primes;

    for(int i = 2; i <= x / i ; i ++)
        while(x % i == 0)
        {
            x /= i;
            primes[i] ++;
        }

    if(x > 1) primes[x] ++;

    LL res = 1;
    for(auto p : primes)
    {
        LL a = p.first, b = p.second;
        LL t = 1;

        while(b --) t = (t * a + 1) % mod;
        res = res * t % mod;
    }

    return res;
}

1.3欧几里得算法：求最大公约数

原理：辗转相除法

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

1.4欧拉函数

欧拉定理：若a与n互质，则 $a^{\varphi(n)}\equiv 1 (mod n)$

1.4.1欧拉函数 O($\sqrt{a}$)

定义：对于正整数n，欧拉函数是小于等于n的正整数中与n互质的数的数目，记作$\varphi(n)$,其中有$\varphi(1) = 1$。

公式：$\varphi(n) = n * (1 - \frac{1}{p1}) * (1 - \frac{1}{p2}) * \cdots * (1 - \frac{1}{pn})$

原理：容斥原理

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

    return res;
}

1.4.2线性筛欧拉函数 O(n)

1.如果i为质数，则 phi[i] = i - 1

2.如果 i % primes[j] == 0, 则 phi[primes[j] * i] = primes[j] * phi[i]

3.如果 i % primes[j] != 0, 则 phi[primes[j] * i] = (primes[j] - 1) * phi[i]

void get_eulers(int n)
{
    phi[1] = 1;
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])
        {
            primes[cnt ++] = i;
            phi[i] = i - 1;
        }

        for(int j = 0; primes[j] * i <= n; j ++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)
            {
                phi[primes[j] * i] = primes[j] * phi[i];
                break;
            }
            phi[primes[j] * i] = (primes[j] - 1) * phi[i];
        }
    }
}

1.5扩展欧几里得算法

对于 a * x + b * y = gcd(a, b), 求x和y

对于求解更一般的方程 a * x + b * y = c, 设 d = gcd(a, b) , 则其有解当且仅当 d | c

int exgcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;

    return d;
}

1.6快速幂&龟速乘

1.3.1快速幂 O(logk)

费马小定理：对于质数p，a为任意自然数，有 $a^{n - 1} \equiv 1 (mod n)$

int qmi(int a, int k, int mod)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }

    return res;
}

ps

1.a需要大于零（貌似）

2.a如果过大，避免溢出可以先将a % p，但是不能将 k % p

1.3.2龟速乘 O(logb)

int qmul(int a, int b, int mod)
{
    int res = 0;
    while(b)
    {
        if(b & 1) res = ((LL)res + a) % mod;
        a = ((LL)a + a) % mod;
        b >>= 1;
    }

    return res;
}

1.7中国剩余定理

1.7.1中国剩余定理

int n;
int A[N], B[N];

int exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;

    return d;
}

int main()
{
    scanf("%d", &n);

    LL M = 1;
    for(int i = 0; i < n; i ++)
    {
        scanf("%d%d", &A[i], &B[i]);
        M *= A[i];
    }

    LL res = 0;
    for(int i = 0; i < n; i ++)
    {
        LL Mi = M / A[i];
        LL ti, x;
        exgcd(Mi, A[i], ti, x);
        res += B[i] * Mi * ti;
    }

    cout << (res % M + M) % M << endl;

    return 0;
}

1.7.2扩展中国剩余定理

即 不需要m1 m2 … mn互质

思路，每次将两个式子化成一个式子

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }

    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;

    return d;
}

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

    LL x = 0, a1, m1;
    cin >> a1 >> m1;
    for(int i = 0; i < n - 1; i ++)
    {
        LL a2, m2;
        cin >> a2 >> m2;

        LL k1, k2;
        LL d = exgcd(a1, a2, k1, k2);

        if((m2 - m1) % d != 0)
        {
            x = -1;
            break;
        }

        k1 *= (m2 - m1) / d; // 获得特解

        LL t = a2 / d;
        k1 = (k1 % t + t) % t; // 在通解中找到最小的解

        x = k1 * a1 + m1; // 目前两个方程合并完后的x的特解

        LL a = a1 / d * a2; // a1 a2的最小公倍数
        m1 = k1 * a1 + m1;
        a1 = a;
    }

    if(x != -1) x = (m1 % a1 + a1) % a1; // 最小正整数解

    cout << x << endl;

    return 0;
}