编程常用的数学

编程 数学 所有文稿

筛法求素数

• 用bool型数组，减少储存空间

#include <iostream>
#include <cmath>
#include <string.h>
using namespace std;
const int maxn=10000;
bool a[maxn];
long long n;
int main(){
    memset(a,true,sizeof(a));
    cin>>n;
    for(int i=2;i<=n;i++){
        if(a[i]){
            cout<<i<<endl;
            for(int j=2*i;j<=n;j+=i) a[j]=false;
        }
    }
    return 0;
}

gcd

欧几里得：辗转相除法

int gcd(int a, int b){//最大公因数
    return b == 0 ? a : gcd(b, a%b);
}

用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数

int g = a[0];
for(int i = 1; i < n; i++){
    g = gcd(g, a[i]);
}

补充：扩展欧几里德算法是用来在已知a, b求解一组p，q使得p * a+q * b = Gcd(a, b) (解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。在包子凑数中运用到过。

lcm(a,b) = a*b/gcm(a*b);

多个数的最小公倍数，先将两个数的最小公倍数求出，再与后面的数求最小公倍数。两个数的最小公倍数，可以先将两个数相乘再除两个数的最小公因数。为了避免溢出，可以先相除再相乘。

快速幂和模运算

模运算性质：

$(A+B)\mod b=(A\mod b+B\mod b)\mod b$

$(A×B)\mod b = ((A\mod b) × (B\mod b))\mod b$

int quickPower(int a, int b, int m)//求a的b次方
{
    if(b==0) return 1%m;//注意b为0的情况
    int ans = 1, base = a;
    while(b > 0)//b是一个变化的二进制数，如果还没有用完
    {
        if(b & 1){//&是位运算，b&1表示b在二进制下最后一位是不是1
            ans *= base;//base自乘，由a^(2^n)变成a^(2^(n+1))
            ans %= m;//结果与“先乘到最后，再取余”的结果一样
        }
        base*=base;
        base%=m;
        b >>= 1;//位运算，b右移一位
    }
    return ans;
}

第一次施工 -2019.3.22
2019.4.5