数论

算法入门与进阶
发布日期:   2021-04-05
更新日期:   2021-06-05
文章字数:   1.9k
阅读时长:   10 分
阅读次数:  

一、高精度计算

二、数论入门

三、模运算

四、快速幂

位运算快速幂

思想

将指数表示成二进制的形式;
一个十进制的数它的数值必然  大于等于 它的二进制表达式的位数；
故可利用二分思想，将二进制数 依次右移并且判断最后一位数是否为1 (为1表示为奇数) ；
相比于线性时间O(n),该方法时间复杂度为O(log n)， 远远快于 O(n);

代码如下


#define N 2
typedef long long ll;
const ll mod = 1e9 + 7;


ll Counting(ll base, ll n) { //快速幂 
    ll power = 1; //幂也就是结果
    while (n) {
        if (n & 1) power *= base; //判断最后一位二进制数是否为1
        base *= base；
        n >>= 1; //去除最后一位二进制数
    }
    return power;
}

矩阵快速幂

矩阵快速幂利用快速幂的思想，也就是二分思想把矩阵对半进行乘法；


//矩阵快速幂

struct Matrix { //定义结构体矩阵
    ll matrix[N][N];c
    Matrix( ) { //构造函数初始化矩阵
        memset(matrix, 0, sizeof(matrix)); //
    }
};


//矩阵乘法 Matrix multiplication
Matrix Matrix_multiplication(Matrix const &A, Matrix const &B) {
    Matrix C;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                C.matrix[i][j] = (C.matrix[i][j] + A.matrix[i][k] * B.matrix[k][j]) % mod;
            }
        }
    }
    return C;
}


//矩阵快速幂
Matrix Counting(Matrix const &base, ll n) { //快速幂
    Matrix power, temp = base;; //幂
    for (int i = 0; i < N; i++) {
        power.matrix[i][i] = 1; //初始化为单位矩阵；
    }
    //与快速幂同理
    while (n) {
        if (n & 1) power = Matrix_multiplication(temp, power);
        temp = Matrix_multiplication(temp, temp);
        n >>= 1;
    }
    return power;
}

应用


#include <bits/stdc++.h>

using namespace std;

#define N 2 //矩阵的阶数
typedef long long ll;
const int mod = 1e9 + 7; //数太大进行模

struct Matrix { //定义结构体矩阵
    ll matrix[N][N];
    Matrix( ) { //构造函数初始化矩阵
        memset(matrix, 0, sizeof(matrix)); //
    }
};
//矩阵乘法 Matrix multiplication
Matrix Matrix_multiplication(Matrix const &A, Matrix const &B) {
    Matrix C;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                C.matrix[i][j] = (C.matrix[i][j] + A.matrix[i][k] * B.matrix[k][j]) % mod;
            }
        }
    }
    return C;
}
//矩阵快速幂
Matrix Counting(Matrix const &base, ll n) { //快速幂
    Matrix power, temp = base;; //幂
    for (int i = 0; i < N; i++) {
        power.matrix[i][i] = 1; //初始化为单位矩阵；
    }
    //与快速幂同理
    while (n) {
        if (n & 1) power = Matrix_multiplication(temp, power);
        temp = Matrix_multiplication(temp, temp);
        n >>= 1;
    }
    return power;
}
//矩阵的输入 
void Matrix_input(Matrix &A) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%lld", &A.matrix[i][j]);
        }
    }
}
//矩阵的输出 
void Matrix_inout(Matrix const &A) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%lld ", A.matrix[i][j]);
        }
        cout << endl;
    }
}
int main() {
    ll n;
    cin >> n; // 矩阵的指数
    Matrix A, matrix_power, C;
    Matrix_input(A); //输入矩阵A
    cout << endl;
    //C = A;
    clock_t start1, end1;
    //clock_t start2, end2;
    start1 = clock();
    matrix_power = Counting(A, n);
    end1 = clock();

//    start2 = clock();
//    for (int i = 1; i < n; i++) {
//        C = Matrix_multiplication(C, A);
//    }
//    en2 = clock();
    
    Matrix_inout(matrix_power); //输出矩阵
    cout << endl;
    //Matrix_inout(C);
    
    cout << "t1 = " << (double)(end1 - start1) / CLOCKS_PER_SEC << "s" << endl; //计算运行时间
    //cout << "t2 = " << (double)(end2 - start2) / CLOCKS_PER_SEC << "s" << endl;
    
    return 0;
}

Fibonacci数列矩阵快速幂

Fibonacci数列
f(n) = f(n - 1) + f(n - 2);
f(1) = f(2) = 1;

我发现 矩阵

Matrix[2][2] = {
    0, 1,
    1, 1
};

有以下规律

矩阵与斐波那契数列有密切关系:

矩阵Matrix 0次方为；

cMatrix[2][2] = {
    1, 0,
    0, 1
};
f(1) = Matrix[1][1] = 1;
f(2) = Matrix[0][1] + Matrix[1][0] = 1;

矩阵Matrix 一次方为；

Matrix[2][2] = {
    0, 1,
    1, 1
};
f(1) = Matrix[0][1] = Matrix[1][0] = 1;
f(2) = Matrix[1][1] = 1;
f(3) = Matrix[0][1] + Matrix[1][1] = 2;

矩阵Matrix 二次方为：

Matrix[2][2] = {
    1, 1,
    1, 2
};
f(1) = Matrix[0][0] = 1;
f(2) = Matrix[0][1] = Matrix[1][0] = 1;
f(3) = Matrix[1][1] = 2;
f(4) = Matrix[0][1] + Matrix[1][1] = 3;

矩阵Matrix 三次方为：

Matrix[2][2] = {
    1, 2,
    2, 3
};
f(2) = Matrix[0][0] = Matrix[0][0];
f(3) = Matrix[0][1] = Matrix[1][0] = 2;
f(4) = Matrix[1][1] = 3;
f(5) = Matrix[0][1] + Matrix[1][1] = 5;

​

矩阵Matrix 四次方为：

Matrix[2][2] = {
    2, 3,
    3, 5
};
f(3) = Matrix[0][0] = 2;
f(4) = Matrix[0][1] = Matrix[1][0] = 3;
f(5) = Matrix[1][1] = 5;
f(6) = Matrix[0][1] + Matrix[1][1] = 8;

矩阵Matrix 五次方为：

Matrix[2][2] = {
    3, 5,
    5, 8
};
f(4) = Matrix[0][0] = 3;
f(5) = Matrix[0][1] = Matrix[1][0] = 5;
f(6) = Matrix[1][1] = 8;
f(7) = Matrix[0][1] + Matrix[1][1] = 13;

矩阵Matrix 六次方为：

Matrix[2][2] = {
    5, 8,
    8, 13
};
f(5) = Matrix[0][0] = 5;
f(6) = Matrix[0][1] = Matrix[1][0] = 8;
f(7) = Matrix[1][1] = 13;
f(8) = Matrix[0][1] + Matrix[1][1] = 21；
综上所述

矩阵Matrix n次方为： 若 n >= 2;

Matrix[2][2] = {
    f(n - 1), f(n),
    f(n), f(n + 1)
};
f(n - 1) = Matrix[0][0];
f(n) = Matrix[0][1] = Matrix[1][0];
f(n + 1) = Matrix[1][1] = 13;
f(n + 2) = Matrix[0][1] + Matrix[1][1];

矩阵Matrix n次方为： 若 n >= 1， 且f(0) = 0; 则有

Matrix[2][2] = {
    f(n - 1), f(n),
    f(n), f(n + 1)
};
f(n - 1) = Matrix[0][0];
f(n) = Matrix[0][1] = Matrix[1][0];
f(n + 1) = Matrix[1][1] = 13;
f(n + 2) = Matrix[0][1] + Matrix[1][1];

故代码如下：


#include <bits/stdc++.h>

using namespace std;

#define N 2 //矩阵的阶数
typedef long long ll;
const int mod = 1e9 + 7; //数太大进行模

struct Matrix { //定义结构体矩阵
    ll matrix[N][N];
    Matrix( ) { //构造函数初始化矩阵
        memset(matrix, 0, sizeof(matrix)); //
    }
};


//矩阵乘法 Matrix multiplication
Matrix Matrix_multiplication(Matrix const &A, Matrix const &B) {
    Matrix C;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                C.matrix[i][j] = (C.matrix[i][j] + A.matrix[i][k] * B.matrix[k][j]) % mod;
            }
        }
    }
    return C;
}
//矩阵快速幂
Matrix Counting(Matrix const &base, ll n) { //快速幂
    Matrix power, temp = base;; //幂
    for (int i = 0; i < N; i++) {
        power.matrix[i][i] = 1; //初始化为单位矩阵
    }
    //与快速幂同理
    while (n) {
        if (n & 1) power = Matrix_multiplication(temp, power);
        temp = Matrix_multiplication(temp, temp);
        n >>= 1;
    }
    return power;
}

int main() {

    /*
    ll matrix_temp[2][2] = {
        0, 1,
        1, 1
    };
    */
    Matrix matrix_temp;
    matrix_temp.matrix[0][0] = 0;
    matrix_temp.matrix[0][1] = 1;
    matrix_temp.matrix[1][0] = 1;
    matrix_temp.matrix[1][1] = 1;
    
    

//    ll matrix_fibonacci[1][2] = {
//        1,//f(1) = 1; == f(n - 1);
//        1 //f(2) = 1; == f(n);
//    };
    ll n;// 矩阵的指数
    while (cin >> n) {
        cout << endl;
        Matrix matrix_power;
        matrix_power = Counting(matrix_temp, n);
        
        printf("f(%lld) = %lld\n", n - 1, (ll)(matrix_power.matrix[0][0] % mod));
        printf("f(%lld) = %lld\n", n, (ll)(matrix_power.matrix[0][1] % mod));
    //    printf("f(%lld) = %lld\n", n, (ll)(matrix_power.matrix[1][0] % mod));
        printf("f(%lld) = %lld\n", n + 1, (ll)(matrix_power.matrix[1][1] % mod));
        printf("f(%lld) = %lld\n", n + 2, (ll)((matrix_power.matrix[1][1] + matrix_power.matrix[0][1]) % mod));
        cout << endl;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cout << matrix_power.matrix[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;

练习
http://acm.hdu.edu.cn/showproblem.php?pid=2817 hdu 2817

// AC代码

#include 
#include 

using namespace std;

typedef long long ll;

ll Counting(ll base, ll n) { //快速幂 
    ll power = 1; //幂也就是结果
    while (n) {
        if (n & 1) power = (power * base) % 200907; //判断最后一位二进制数是否为1
        base = (base * base) % 200907;
        n >>= 1; //去除最后一位二进制数
    }
    return power % 200907;
}

int main() {
    int n;
    ll a, b, c, k;
    cin >> n;
    while (n--) {
    
        scanf("%lld %lld %lld %lld", &a, &b, &c, &k);
        if(c + a == 2 * b) {
            ll d = (b - a) % 200907;
            ll t = ((a % 200907) + ((k - 1) % 200907) * d) % 200907;
            cout << t << endl;
        } else {
            ll q = b / a;
            cout << a * Counting(q, k - 1) % 200907 << endl;
        }
    }
    return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=1061 hdu 1061

//AC代码

#include 

using namespace std;

typedef long long ll;

const ll mod = 10;

ll Counting(ll base, ll n) {
    ll power = 1;
    while (n) {
        if (n & 1) power = power * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return power;
}

int main() {
    int t;
    cin >> t;
    ll n;
    while (t--) {
        scanf("%lld", &n);
        int temp = Counting(n, n) % 10;
        printf("%d\n", temp);
    }
    return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=5392 hdu5392 目前不会，置换群幂运算，表示不懂。



五、GCD、LCM

1、GCD

原理

利用辗转相除法

代码实现如下


typedef long long ll;

//法一  迭代法 
ll gcd(ll a, ll b) { //默认a > b; 
    
    while (b) {
        ll temp = a;
        a = b;
        b = temp % b;
    }
    
    return a;
    
}

// 法二 递归法

ll gcd_1(ll a, ll b) { //默认a > b;

    return b ? gcd_1(b, a % b) : a;
    
}

验证


#include 
#include 

using namespace std;

typedef long long ll;

//法一  迭代法 
ll gcd(ll a, ll b) { //默认a > b; 
    
    while (b) {
        ll temp = a;
        a = b;
        b = temp % b;
    }
    return a;
}

// 法二 递归法

ll gcd_1(ll a, ll b) { //默认a > b;
    return b ? gcd_1(b, a % b) : a;
} 

int main() {
    ll a, b;
    while (cin >> a >> b) {
        
        cout << __gcd(a, b) << endl; // C++内置函数 头文件 
        cout << gcd(a, b) << endl;  // d迭代 
        cout << gcd_1(a, b) << endl;  //递归 
         
    }
    return 0;
}

**实现了GCD, LCM不就简单了么. **

原理：

最小公倍数为 a * b / gcd(a, b)


ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b; // 防止 a * b 溢出；
}

六、扩展欧几里得算法与一元二次方程的整数解

七、同余与逆元

八、素数

1、快速线性筛

快速线性筛法没有冗余，不会重复筛除一个数，所以几乎是线性的。
虽然从代码上分析，时间复杂度并不是O(n)，而是接近线性而已。


void init(int n) {
    for (int i = 2; i <= n; i++) {
        if (!prime[i]) prime[++prime[0]] = i;  //prime[0]存储素数个数，顺便把素数按顺序存储；
        for (int j = 1; j <= prime[0]; j++) {
            if ( i * prime[j] > n) break;
            prime[i * prime[j]] = 1; //标记合数
            if (!(i % prime[j])) break; // 减少重复标记
        }
    }
}

九、组合数学

十、鸽巢原理

十一、杨辉三角与二项式系数

十二、容斥原理

十三、Fibonacci数列

十四、母函数

十五、特殊计数

十六、概率与数学期望

十七、公平组合游戏

十八、巴什游戏与P-position、 N-position

十九、尼姆游戏

二十、图游戏与Sprague-Grundy

二十一、威佐夫游戏

文章作者: Axieyun
文章链接: https://Axieyun.top/posts/2230.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Axieyun !
算法入门与进阶
赏
评论
评论
  目录