数学

发表于 2023-02-28 分类于算法

最大公约数、质数（埃氏筛，线性筛）、快速幂、矩阵快速幂

0.1 质数

prime number：质数，素数。在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。否则称为合数。
composite number：合数

0.1.1 暴力枚举

class Solution {
public:
    bool isPrime(int x) {
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    int countPrimes(int n) {
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            ans += isPrime(i);
        }
        return ans;
    }
};

0.1.2 埃氏筛

如果 x 是质数，那么大于 x 的倍数2x,3x,… 一定不是质数

const int MX=1e5;
vector<bool> isPrime(MX,true);
auto init=[]{
	isPrime[1]=false;
	for(int i=2;i<=MX;i++){
		if(isPrime[i]){
			for(int j=i*i;j<=MX;j+=i){
				isPrime[j]=false;
			}
		}
	}
	return 0;
}();


class Solution {
public:
    int countPrimes(int n) {
        vector<int> isPrime(n,1);//初始标记为质数
        int ans=0;
        for(int i=2;i<n;i++){
            //对于质数才需要进行筛选
            if(isPrime[i]){
                ans++;
                if((long)i*i<n){
                    for(int j=i*i;j<n;j+=i)
                        isPrime[j]=0;
                }
            }
             
        }
        return ans;
    }
};

0.1.3 线性筛

$$
如果x可以被primes_i整除，对于合数y=x.primes_{i+1}={\frac{x}{primes_i}primes_{i+1}}primes_i
$$

class Solution {
public:
    int countPrimes(int n) {
        vector<int> primes;
        vector<int> isPrime(n, 1);
        for (int i = 2; i < n; ++i) {
            if (isPrime[i]) {
                primes.push_back(i);
            }
            for (int j = 0; j < primes.size() && i * primes[j] < n; ++j) {
                isPrime[i * primes[j]] = 0;
                if (i % primes[j] == 0) {
                    break;
                }
            }
        }
        return primes.size();
    }
};

1 最大公约数(GCD)

1.1 欧几里得算法

gcd(m,n)=gcd(n,m mod n)

假设x是m，n的最大公约数，且m大于n（m小于n时，上式实现两个数的交换）

m=(m/n)*n+m%n（ / 表示整除）

n=(n/x)*x

则，则(m/n)*n有约数x，又m有约数x，则m%n也可以被x整除

#include <iostream>
using namespace std;
int Euclid(int m, int n)
{
    while (n)
    {
        int t = m % n;
        m = n;
        n = t;
    }
    return m;
}
int main()
{
    cout << Euclid(60, 24) << endl;
}

1.2 连续整数检测算法

从m、n中较小的数开始查找，直到找到可以被m、n都整除的数

#include <iostream>
using namespace std;
int gcd(int m, int n)
{
    int t = min(m, n);
    while (m % t != 0 || n % t != 0)
        --t;
    return t;
}
int main()
{
    cout << gcd(60, 24) << endl;
}

1.3 求m、n的质因数

abc

算法设计与分析基础（ch1）

求不大于整数n的连续质数序列：

埃拉托色尼筛选法（sieve of Eratosthenes）

#include <iostream>
#include <vector>
using namespace std;
//埃拉托色尼筛选法，产生一个不大于给定整除n的连续质数序列
void Sieve(int n, vector<int> &isPrime)
{
    for (int i = 2; i * i <= n; ++i)
    {
        if (isPrime[i])
        {
            int t = i * i;
            while (t <= n)
            {
                isPrime[t] = 0;
                t = t + i;
            }
        }
    }
}
int gcd(vector<int> &isPrime, int m, int n)
{
    int result = 1;
    for (int i = 2; i <= n; ++i)
    {
        //如果i是质数
        if (isPrime[i])
        {
            while (m % i == 0 && n % i == 0)
            {
                m = m / i;
                n = n / i;
                result *= i;
            }
        }
    }
    return result;
}
int main()
{
    int m, n;
    cin >> m >> n;
    vector<int> isPrime(min(m, n) + 1, 1); //记录较小数的质数序列
    // cout << isPrime.size() << endl;
    Sieve(min(m, n), isPrime);
    cout << gcd(isPrime, max(m, n), min(m, n)) << endl;
}

2 最小公倍数（LCM）

$$
LCM(m,n)=\frac{m*n}{GCD(m,n)}
$$

3 容斥原理

4 快速幂

//计算a^b%m
   int helper(int a,int b,int m){
       int res=1;
       int factor=a;
       while(b){
           if(b&1){
               res=(res*factor)%m;
           }
           factor=factor*factor%m;
           b=(b>>1);
       }
       return res;
   }

5 矩阵快速幂

70. 爬楼梯 - 力扣（LeetCode）

class Solution {
public:
    int climbStairs(int n) {
        vector<vector<long long>> ret{{1,1},{1,0}};
        vector<vector<long long>> ans=matrixPow(ret,n);
        return ans[0][0];
    }
    //计算矩阵a的n次方
    vector<vector<long long>> matrixPow(vector<vector<long long>>&a,int n){
        vector<vector<long long>> ret={{1,0},{0,1}};
        while(n){
            if(n%2==1){
                ret=multiply(ret,a);
            }
            a=multiply(a,a);
            n=n/2;
        }
        return ret;
    }
    // 计算两个矩阵相乘
    vector<vector<long long>> multiply(vector<vector<long long>>& a,vector<vector<long long>>& b){
        vector<vector<long long>> ans(2,vector<long long>(2));
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    ans[i][j]+=a[i][k]*b[k][j];
                }
            }
        }
        return ans;
    }
};

6 正整数技巧

对于正整数，$xy>=success$等价于$x\ge \left \lceil \frac{success}{y} \right \rceil$ 也等价于$x> \left \lceil \frac{success-1}{y} \right \rceil$

2300. 咒语和药水的成功对数

6.1.1 计算上界

$$
\left \lceil \frac{pile}{speed} \right \rceil
=\left \lfloor \frac{pile+speed-1}{speed} \right \rfloor
=\left \lfloor \frac{pile-1}{speed} \right \rfloor+1\
=\left \lfloor \frac{pile}{speed} \right \rfloor+(pile%speed !=0)
$$

6.1.2 同余定理

$$
\begin{align}
(s[R]-S[L])%mk\ s[R]%m-S[L]%mk \quad s[R]%m-S[L]%m+mk\ s[R]%m-kS[L]%m \quad s[R]%m+m-kS[L]%m\ \rightarrow (s[R]%m-k+m)%ms[L]%m
\end{align}
$$

$$
s为负数情况取余数： x=(s%k+k)%k
$$

7 幂

32 位有符号整数的范围内：

最大的 3 的幂为 $2^{30}$
最大的 3 的幂为 $3^{19}=1162261467$

231. 2 的幂

2的幂二进制表示中最高位为，其余位为0

只含因子2，

$2^{30} mod: x==0$

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0&&(n&(n-1))==0;
    }
    bool isPowerOfTwo(int n) {
        if(n==0)
            return false;
        while(n%2==0)
            n/=2;
        return n==1;
    }
    
    const int BIG=pow(2,30);
    return n>0&&BIG%n==0;
};

class Solution {
public:
    bool isPowerOfTwo(int n) {
        long long cur=1;
        while(cur<n){
            cur*=2;
        }
        return cur==n;
    }
};

342. 4的幂

不能用2**30模4为0来判断，因为是2的幂也可以。

class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
   //2的幂满足性质，4的幂满足性质 
     return n > 0 && (n & (n - 1)) == 0&& sqrt(n)*sqrt(n)==n;
};

7.2 函数

7.2.1 对数

$$
log_an=log_ab*log_bn=lob_ba/log_bn
$$
换底公式：
$$
log_bN=log_aN/log_ab\
log_bN=X\
b^X=N\
log_ab^X=log_aN\
Xlog_ab=log_aN
$$

7.2.2 幂函数

$x^a$

7.2.3 指数函数

$a^x$

8 离散数学

8.1 二元关系

8.1.1 次序关系

偏序

如果集合A上的二元关系R是自反的、反对称的和传递的，那么称R为A上的偏序，称序偶<A,R>为偏序集合。

9 单位

皮秒：$1ps=10^{-12}s$