数论

质数

约数

欧拉函数

欧几里得

高斯消元

中国剩余定理

容斥原理

博弈论

组合数求法

预处理之后进行询问的时间复杂度为 O（1）；

1，对于询问次数较多，并且给定 ab 不大的值，可以利用递推进行预处理，处理出 从 C11 到 Cab 的值 n2

利用了公式 $$ C[a][b] = c[a-1][b] + c[a-1][b-1] $$

1≤n≤100001≤n≤10000, 1≤b≤a≤2000

#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
const int N = 2010;
int c[N][N];
void init()
{
    c[1][1] = 1;
    for(int i = 0;i<  N ; i ++)
        for(int j = 0; j <= i ; j++)
        if(!j) c[i][j] = 1;
        else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;
}
int main(void)
{
    init();
    int n;
    cin >> n;
    while(n--)
    {
        int a,b;
        cin >> a >> b;
        cout << c[a][b] << endl;
    }
    return 0;
}

2，对于询问次数不算特别多，并且给定 ab 的值较大的值，可以利用组合数的逆推（上下阶乘） 方式，预处理出来 分子的阶乘和分母的阶乘的逆元，然后直接利用公式输出 res 即可 nlogn $$ C[a][b] = a! / (b! * (a - b)!) $$

1≤n≤100001≤n≤10000, 1≤b≤a≤105

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int fact[N],infact[N];
int qmi(int a,int k,int p)
{
    int res = 1 % p;
    while(k)
    {
        if(k & 1) res =(LL) res * a % p;
        a = (LL) a * a % p;
        k = k >> 1;
    }
    return res;
}
int main(void)
{
    fact[0] = infact[0] = 1;
    for(int i = 1;  i< N ; i ++)
    {
        fact[i] = (LL)i * fact[i-1] % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i,mod-2,mod) % mod;
    }
    int n;
    cin >> n;
    while(n --)
    {
        int a,b;
        cin >> a >> b;
        cout << (LL)fact[a] * infact[b] % mod * infact[a-b] % mod<< endl;
    }
    return 0;
}

3，对于询问次数不多，给出 ab 的值特别大的值，可以利用 lucase 定律来求，Cab = Ca%pb%p * Ca/pb/p；这里需要注意的点主要是 返回 lucase 定律的值必须时 lucasa/p,b/p 因为 可能再 ab 除以 p 之后的到的值仍然大于大于p，这样的话求 Cab 可能会出现错误；

求 Cab 时利用的公式是分母到分子的阶乘比上分子从一到它本身的阶乘利用逆元来求

$$ Cba=a!/b!(a−b)!=(a−b+1)×(a−b+2)×…×a/b! $$

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;


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 C(int a, int b, int p)
{
    if (b > a) return 0;

    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- )
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2, p) % p;
    }
    return res;
}


int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}


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

    while (n -- )
    {
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}

4，对于所求的值不进行 取模的运算

分为三步走，第一步用质数筛法，筛出前n个数中的质数，第二步，利用除法求出每个数质因数的倍数的个数，然后利用高精度乘法求出最终p的结果

上面的数的阶乘和下面两个数的阶乘都可以用数学基本定理来分解

然后再上下再去掉相同的指数再相乘就行

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 5010;
int primes[N];
bool st[N];
int cnt;
int sum[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;
        }
    }
}
int get(int x,int p)
{
    int res = 0;
    while(x)
    {
        res += x/p;
        x /= p; // 一直把 p 的 k 次方也去掉
    }
    return res;
}
vector<int> mul(vector<int> a,int b)
{
    vector<int> c;
    int t = 0;
    for(int i = 0;i<a.size();i++)
    {
        t = t + a[i] *b;
        c.push_back(t%10);
        t = t/10;
    }
    while(t)
    {
        c.push_back(t%10);
        t = t /10;
    }
    return c;
}
int main(void)
{
    int a,b;
    cin >> a>> b;
    get_primes(a); // 筛选出了质数
    for(int i = 0;i < cnt;i++)
    {
        int p = primes[i];
        sum[i] = get(a,p) - get(a-b,p) - get(b,p);// 这里枚举所有可能存在的质数 并除去 得到除之后的质数的数量；；
    }
    vector<int> res;
    res.push_back(1);
    for(int i = 0;i<cnt;i++)
        for(int j = 0;j<sum[i];j++)
            res = mul(res,primes[i]); // 这里进行相乘；；
    for(int i = res.size() -1; i>=0;i--) cout << res[i];
    cout << endl;
    return 0;
}

质数

试除法求质数

可以利用 n/i 来进行优化，因为所有的约数都是一对一对的出现的，d 能整除 n ，n/d 也能整除 n ，所以说就可以进行优化，把 n 换成 n/i 来缩小范围 ： 如果 n/i 之后存在树使 x 不为质数，那么，在 n/i 之前一定也存在这样的数

#include <iostream>
#include <algorithm>
using namespace std;
bool check(int x)
{
    if(x == 2 ) return true;
    if(x == 1 || x == 0) return false;
    for(int i = 2; i <= x / i ; i ++)
    {
        if(x % i == 0) return false;
    }
    return true;
}
int main(void)
{
    int n;
    cin >> n;
    while(n --)
    {
        int x;
        cin >> x;
        if(check(x)) cout << "Yes" << endl;
        else cout <<"No" << endl;
    }
    return 0;
}

分解质因数

由算术基本定理可以知道，任何一个数都可以分解为质数的指数形式的乘积和

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
void get_primes(int x)
{
    for(int i =2 ; i <= x / i ; i ++)
    {
        if(x%i == 0)
        {
            int s = 0;
            while( x % i == 0) {
                s++;
                x = x / i;
            }
            cout << i << " " << s << endl;
        }
    }
    if(x > 1) cout << x <<" " << 1 << endl;
    cout << endl;
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int x;
        cin >> x;
        get_primes(x);
    }
    return 0;
}

筛质数

朴素做法是筛掉所有数后面的数

埃式筛法是筛掉所有质数后面的数

线性筛法是通过质因子来筛掉所有质数后面的数 1e7 会比上一个快一倍

线性筛法 判断条件 if 成立时保证了 i 的最小质因子是 pj ，同时 i*pj 的最小质因子也是 pj

当 if 条件不成立时，保证了 i*pj 的最小质因子是 pj；且 pj 一定小于 i 的所有质因子

每个合数都会有一个最小质因子，当 i 枚举到 x/i 的时候，x 一定会被筛掉

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 +10;
bool st[N];
int primes[N],cnt;
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[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
}
int main(void)
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

约数

试除法求约数

可以利用 i != n/i 来进行优化 ，因为质数是一对一对的出现的，所以可以用这个式子进行提前的判断，得到大于 n/i 的约数，并且可以防止出现平方数相同的情况

#include <iostream>
#include <algorithm>
using namespace std;
void get_divisors(int x)
{
    vector<int> res ;
    for(int i = 1 ; i <= x/ i; i ++)
    {
        if(x % i ==0)
        {
            res.push_back(i);
            if(i != x/i) res.push_back(x/i);
        }
    }
    sort(res.begin(),res.end());
    for(auto x : res) cout << x << " " ;
    cout << endl;
}
int main(void)
{
    int n;
    cin >> n;
    while(n --)
    {
        int x;
        cin >> x;
        get_divisors(x);
    }
    return 0;
}

约数个数

一个数可以根据算术基本定理进行划分，划分之后，约数的个数就是 所有指数项+1 的乘积和；

因为这个数的每一个数也都可以利用算术基本定里进行划分，得到不同的质数的指数，所以需要进行 +1

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int mod = 1e9 + 7;
int n;
unordered_map<int,int>primes;
void get(int x)
{

    for(int i = 2; i <= x/ i; i++)
    {
        if(x % i == 0)
        {
            while(x % i == 0) primes[i]++,x/=i;
        }
    }
    if(x > 1) primes[x] ++;
}
int main(void)
{
    cin >> n;
    while(n --)
    {
        int x;
        cin >> x;
        get(x);

    }
    long long res = 1;
    for(auto prime : primes) res = (long long ) res * (prime.second + 1)  % mod;
    cout << res << endl;
    return 0;
} 

约数之和

一个数可以根据算术基本定理进行划分，划分之后，每个质数的从零次方到这个质数指数的乘积和再相乘之后的到约数的之和

因为每个数都可以利用算术基本定理进行划分，上面的乘积式，乘开之后从零次方到他指数次方的所有结果都会出现，又因为是乘积式所以会进行累加从而得到最后的结果

从0次方到b次方的乘积

t = (t * a + 1)循环 b 次，t 从 1 开始

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 1e9 +7;
unordered_map<int,int> primes;
void get(int x)
{
    for(int i = 2;i <= x/i;i++)
    {
        while(x%i == 0)
        {
            x = x / i;
            primes[i]++;
        }
    }
    if(x > 1) primes[x] ++;
}
int main(void)
{
    int n;
    cin >> n;
    while(n--)
    {
        int x;
        cin >> x;
        get(x);
    }
    LL res = 1;
    for(auto prime : primes)
    {
        LL a = prime.first;
        LL b = prime.second;
        LL t = 1; 
        while(b -- ) t = (t * a + 1) % mod; // Important;;
        res = res * t %mod;
    }
    cout << res << endl;
    return 0;
}

最大公约数

d 能整除 a，d 能整除 b，d 就能整除 a+b，d 就能整除 ax+by

因此 a 和 b 的最大公约数就等与 b 和 a%b 的最大公约数

因为 a %b 可以看成 a - c*b

再由上面的式子得出结果即可

#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a,int b)
{
    return b ? gcd(b,a%b) : a;
}
int main(void)
{
    int n;
    cin >> n;
    while(n--)
    {
        int a,b;
        cin >> a >> b;
        cout << gcd(a,b) <<endl;
    }
    return 0;
}

最小公倍数

就是 a*b / gcd(a,b);

#include <iostream>
#include <algorithm>
using namespace std;
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);
}
int main(void)
{
    int n;
    cin >> n;
    while(n--)
    {
        int a,b;
        cin >> a >> b;
        cout << lcm(a,b) <<endl;
    }
    return 0;
}

**欧拉函数 **

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL oula(int x)
{
    LL res = x;
    for(int i = 2;i <= x/i;i++)
    {
        if(x% i == 0)
        {
            while(x % i == 0)
            {
                x = x/i;
            }
            res =  (LL) res / i * (i-1);
        }
    }
    if(x > 1) res = (LL) res / x *(x-1);
    return res;
}
int main(void)
{
    int n;
    cin>> n;
    while(n--)
    {
        int x;
        cin >> x;
        cout << oula(x) <<endl;
    }
    return 0;
}

容斥原理

筛法求欧拉函数

当该数为质数的时候，该数的欧拉函数为 n-1；

线性筛时，若 pj 是 pj*i 的最小质因子时，由欧拉定理可以知道该最小质因子一定乘过了，所以只需要将 e[i] * pj 即可；

若 pj 不是 pj*i 的最小质因子时 需要加上 pj * (pj - 1) / pj 所以得到 e[i] * (pj - 1);

快速幂

把 a 的 k 次方上面的 k 转化成二进制的数 ，然后利用二进制的数来进行相乘求解最终的 ans

利用循环每次使 a 相乘变成指数平方式，同时指数 k 从第零位开始进行向前走，如果末尾等于 1 的话，就把 res * a 相当于了 a 的多少次方相乘进行

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL qmi(int a,int k,int p)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a %p;
        a = (LL)a*a % p;
        k = k >> 1;
    }
    return res;
}
int main(void)
{
    int n;
    cin >> n;
    while(n--)
    {
        int a,k,p;
        cin >> a >> k >> p;
        cout << qmi(a,k,p) << endl;
    }
    return 0;
}

快速幂求逆元

快速幂求逆元，当 b 和 p 互质的时候，根据费马小定理可以得到 b 的 -2 次方就是 b 的逆元

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL qmi(int a,int k,int p)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = (LL)res * a %p;
        a = (LL)a*a % p;
        k = k >> 1;
    }
    return res;
}
int main(void)
{
    int n;
    cin >> n;
    while(n--)
    {
        int a,p;
        cin >> a >> p;
        LL res = qmi(a,p-2,p);
        if(a % p == 0) cout << "impossible" << endl;
        else cout << res << endl;
    }
    return 0;
}

扩展欧几里得求逆元

求出 x 就可以得到 逆元了

扩展欧几里得算法

利用最大公约数来辗转得到最终的结果

当 b 不为 0 的时候就可继续进行 a%b ；

给定 nn 对正整数 ai,biai,bi，对于每对数，求出一组 xi,yixi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)ai×xi+bi×yi=gcd(ai,bi)。

给出 a,b 求出 x,y

#include <iostream>
#include <algorithm>
using namespace std;
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;
}
int main(void)
{
    int n;
    cin >> n;
    while(n--)
    {
        int a,b;
        cin >> a >> b;
        int x,y;
        int d = exgcd(a,b,x,y);
        cout << x<<" " <<  y << endl;
    }
    return 0;
}

输入规模在10的5次方以内，可以用 cin 和 scanf 差别不大

大于 10 的 5 次方之后，用 scanf 可以比 cin 快一倍左右