算法基础课-数学知识

质数

试除法判定质数

#include <iostream>
#include <algorithm>

using namespace std;

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )//不要用开方函数或者i*i小于x。开方函数慢，i*i可能越界
        if (x % i == 0)
            return false;
    return true;
}

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

    while (n -- )
    {
        int x;
        cin >> x;
        if (is_prime(x)) cout << "Yes" << endl;
        else cout << "No" << endl;;
    }

    return 0;
}

分解质因数

//详细得可以看这个题解：https://www.acwing.com/solution/content/27448/
#include <iostream>
#include <algorithm>

using namespace std;

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )//i <= x / i:防止越界，速度大于 i < sqrt(x)
{
        if (x % i == 0)//i为底数
        {
            int s = 0;//s为指数
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;//输出
        }
}
    if (x > 1) cout << x << ' ' << 1 << endl;//如果x还有剩余，单独处理
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        divide(x);
    }

    return 0;
}

筛质数

//线性法时间复杂度为O(n)
//参考这个链接：https://www.acwing.com/solution/content/7950/
#include <iostream>
#include <algorithm>

using namespace std;

const int N= 1000010;

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;
            //当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j]<i的最小质因子,所以primes[j]*i的最小质因子就是primes[j];
            //当有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的最小质因子，此时就应该退出循环，避免之后重复进行筛选。
        }
        
    }
}

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

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

约数

试除法求约数

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        vector<int> res;
        //因为约数成对出现，所以只需要循环到根号x
        // 不要是用 i *i <= n，因为可能溢出
        for(int i = 1; i <= n /i; i++)
        {
            if(n % i == 0)
            {
                res.push_back(i);
                //如果i * i = x,添加i即可，不用添加 x / i
                if(n / i != i)
                    res.push_back(n / i);
            }
        }
        sort(res.begin(), res.end());
        for(auto x : res) cout << x << " ";
        cout << endl;

    }
}

约数个数

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int mod = 1e9+7 ;
//这题只要是考察约数个数的公式
int main()
{
    int T; 
    cin >> T;
    unordered_map<int, int> h;
    while(T--)
    {
        int n; 
        cin >> n;
        //依次求出指数
        for(int i = 2; i <= n / i; i++)
        {
            while(n % i == 0)
            {
                //指数+1
                h[i] ++;
                n = n / i;
            }
        }
        //如果有剩余，也是一个质因子
        if(n > 1) h[n]++;
    }

    long long  res = 1;
    for(auto iter = h.begin(); iter != h.end(); iter++)
    {
        //res = (x1+1)(x2+1)(x3+1)…(xk+1)
        res = res * (iter->second + 1) % mod ;
    }
    cout << res;
}

约数之和

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

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

    unordered_map<int, int> primes;

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

        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;// x^2 + x = x(x + 1);
        //计算一下：
//第一步：
//t = (t * a + 1)
//t=p1的一次方+p1的零次方；

//第二步：
//t = (t * a + 1)
//t=p1的二次方+p1的一次方+1=p1的二次方+p1的一次方+p1的零次方；
        res = res * t % mod;
    }

    cout << res << endl;

    return 0;
}

最大公约数

//这段算法得代码关键是辗转相除法具体可以参考以下链接：https://www.acwing.com/solution/content/145791/
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int a, b;
        cin >> a >> b;
        //辗转相除，直到小括号内右边数为0
        while(b)
        {
            //c 一定小于 b
            int c = a % b;
            //小括号左边放除数，右边放约数
            a = b;
            b = c;
        }
        //小括号内左边数为最大公约数
        cout << a << endl;
    }
}

欧拉函数

欧拉函数

//只是一个数学公式具体推导看这个链接就可以：https://www.acwing.com/solution/content/8702/
#include <iostream>

using namespace std;


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

    return res;
}


int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        cout << phi(x) << endl;
    }

    return 0;
}

筛法求欧拉函数

//不懂的地方看这个代码：https://www.acwing.com/solution/content/3952/
//y总的代码视频讲的也很纤细：https://www.acwing.com/video/299/
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000010;
int primes[N], cnt;
int phi[N];
bool st[N];

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] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
            {
                phi[primes[j] * i] = phi[i] * primes[j]; 
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
}

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

    get_eulers(n);
    LL res = 0;
    for (int i = 1; i <= n; i++) res += phi[i];
    printf("%lld\n", res);
    return 0;
}

快速幂

快速幂

//为什么是Logb得时候复杂度，可以看这个链接：https://www.acwing.com/solution/content/15293/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;



LL quick(LL a,LL b,LL p)//二进制，背就完事
{
    LL res=1;
    while(b>0)
    {
        if(b&1) res=a*res%p; //%p都是为了防止溢出操作
        a=a*a%p;//这里也是，每次乘以得数都不一样
        b>>=1;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int a,b,p;
        scanf("%d%d%d", &a, &b,&p);
        printf("%d\n",quick(a,b,p));
    }
}

快速幂求逆元

//不懂的话，看下链接这篇文章就懂了：https://www.acwing.com/problem/content/878/
#include <iostream>
using namespace std;
typedef long long LL;

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

int main()
{
    int n; cin >> n;
    while(n --){
        int a, p;
        cin >> a >> p;
        if(a % p == 0) puts("impossible");
        else cout << qmi(a, p - 2, p) << endl;
    }
    return 0;
}

扩展欧几里得算法

扩展欧几里得算法

//详细的过程看看这个代码：https://www.acwing.com/solution/content/1393/
#include<bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int &x, int &y){//返回gcd(a,b) 并求出解(引用带回)
    if(b==0){
        x = 1, y = 0;
        return a;
    }
    int x1,y1,gcd;
    gcd = exgcd(b, a%b, x1, y1);
    x = y1, y = x1 - a/b*y1;
    return gcd; 
}
int main(){
    int n,a,b,x,y;
    cin>>n;
    while(n--){
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<" "<<y<<endl;
    }
    return 0;
}

线性同余方程

//证明思路看一下这个链接：https://www.acwing.com/solution/content/5937/
#include<bits/stdc++.h>
using namespace std;
using LL = long long ;
int exgcd(int a, int b, int &x, int &y){//返回gcd(a,b) 并求出解(引用带回)
    if(b==0){
        x = 1, y = 0;
        return a;
    }
    int x1,y1,gcd;
    gcd = exgcd(b, a%b, x1, y1);
    x = y1, y = x1 - a/b*y1;
    return gcd; 
}
int main(){
    int n,a,b,x,y,m;
    cin>>n;
    while(n--){
        cin>>a>>b>>m;
        int d=exgcd(a,m,x,y);
        if (b % d) puts("impossible");
        else 
        {
            x = (LL)x * b / d % m;
            cout << x << endl;
        }
    }
    return 0;
}

中国剩余定理

表达整数的奇怪方式

//这个代码看不懂
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
int n;
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;
}
LL inline mod(LL a, LL b){
    return ((a % b) + b) % b;
}
int main(){
    scanf("%d", &n);
    LL a1, m1;
    scanf("%lld%lld", &a1, &m1);
    for(int i = 1; i < n; i++){
        LL a2, m2, k1, k2;
        scanf("%lld%lld", &a2, &m2);
        LL d = exgcd(a1, -a2, k1, k2);
        if((m2 - m1) % d){ puts("-1"); return 0; }
        k1 = mod(k1 * (m2 - m1) / d, abs(a2 / d));
        m1 = k1 * a1 + m1;
        a1 = abs(a1 / d * a2);
    }
    printf("%lld\n", m1);
    return 0;
}

高斯消元

高斯消元解线性方程组

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;
const double eps = 1e-6;

int n;
double a[N][N];


int gauss()
{
    int c, r;// c 代表 列 col ， r 代表 行 row
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;// 先找到当前这一列，绝对值最大的一个数字所在的行号
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;
        //这一步就找到了最大的行号
        
        if (fabs(a[t][c]) < eps) continue;// 如果当前这一列的最大数都是 0 ，那么所有数都是 0，就没必要去算了，因为它的约束方程，可能在上面几行

        for (int i = c; i < n + 1; i ++ ) swap(a[t][i], a[r][i]);//// 把当前这一行，换到最上面（不是第一行，是第 r 行）去
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];// 把当前这一行的第一个数，变成 1， 方程两边同时除以 第一个数，必须要到着算，不然第一个数直接变1，系数就被篡改，后面的数字没法算
        for (int i = r + 1; i < n; i ++ )// 把当前列下面的所有数，全部消成 0
            if (fabs(a[i][c]) > eps)// 如果非0 再操作，已经是 0就没必要操作了
                for (int j = n; j >= c; j -- )// 从后往前，当前行的每个数字，都减去对应列 * 行首非0的数字，这样就能保证第一个数字是 a[i][0] -= 1*a[i][0];
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;// 这一行的工作做完，换下一行
    }

    if (r < n)// 说明剩下方程的个数是小于 n 的，说明不是唯一解，判断是无解还是无穷多解
    {// 因为已经是阶梯型，所以 r ~ n-1 的值应该都为 0
        for (int i = r; i < n; i ++ )// 
            if (fabs(a[i][n]) > eps)// a[i][n] 代表 b_i ,即 左边=0，右边=b_i,0 != b_i, 所以无解。
                return 2;
        return 1;// 否则， 0 = 0，就是r ~ n-1的方程都是多余方程
    }

    //这一步的解释看看这个链接的评论区：https://www.acwing.com/solution/content/5151/
    // 唯一解 ↓，从下往上回代，得到方程的解
    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[j][n] * a[i][j];//因为只要得到解，所以只用对 b_i 进行操作，中间的值，可以不用操作，因为不用输出

    return 0;
}

int main()
{
    cin >> n;
    
    //处理数据输入
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n + 1; j ++ )
            cin >> a[i][j];

    int t = gauss();

    if (t == 0)
    {
        for (int i = 0; i < n; i ++ ) printf("%.2lf\n", a[i][n]);
    }
    else if (t == 1) puts("Infinite group solutions");
    else puts("No solution");

    return 0;
}

高斯消元解异或线性方程组

#include <iostream>
using namespace std;

const int N = 110;
int a[N][N];
int n;
int gauss()
{
    //第一：消成同解的上三角矩阵
    int r, c;
    //1.枚举列,可以跳过行，但是不能跳过列
    for (r = 0, c = 0; c < n; c++) {
        //2.找到剩余行中的非零行
        int t = r;
        for (int i = r; i < n; i++)
            if (a[i][c]) {
                t = i;
                break;
            }
        if (a[t][c] == 0) continue;
        //3.非零行换到剩余行中的最上面
        for (int i = c; i <= n; i++) swap(a[r][i], a[t][i]);
        //4.剩余行中的第c列下面消成0
        for (int i = r + 1; i < n; i++) {
            if (a[i][c]) {
                for (int j = c; j <= n; j++)
                    a[i][j] ^= a[r][j];
            }
        }
        r++;   
    }   
    //第二：判断解的情况
    if (r < n) {
        for (int i = r; i < n; i++)
            if (a[i][n])
                return 2;
        return 1;
    } else {
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                a[i][n] ^= a[i][j] * a[j][n];
            }
        }
        return 0;
    }

}

int main()
{
    //int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= n; j++)
            cin >> a[i][j];
    int res = gauss();
    if (res == 0) {
        for (int i = 0; i < n; i++)
            cout << a[i][n] << endl;
    } else if (res == 1) 
        cout << "Multiple sets of solutions"<< endl;
    else 
        cout <<   "No solution" << endl;
}

求组合数

求组合数I

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010, mod = 1e9 + 7;


int c[N][N];


void init()
{
    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()
{
    int n;

    init();

    scanf("%d", &n);

    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);

        printf("%d\n", c[a][b]);
    }

    return 0;
}