数学知识

数论主要分为两种数学方法求解

质数
约数

质数的定义

质数是从2开始的自然数，这个数只能有两个约数分别是自己和1，质数又被称为素数

试除判断质数

暴力判断质数

bool pd(int x) {
		if(x < 2) return false;
		for(int i = 2;i < x;i++) {
				if(x % i == 0) return false;
		}
		
		return true;
}

很明显时间复杂度为O(n)还是很高的

优化：我们发现构成非质数的两个数往往都是成对存在的，即x = d * d，这个时候我们只需要判断小的那一部分是否满足条件即可，即i <= n / i

注意

不推荐使用sqrt(x)或者是i * i <= n，sqrt每一次循环都要执行一回，时间复杂度比较高，后面哪种容易溢出，使i * i变成负数

bool pd(int x) {
		if(x < 2) return false;
		for(int i = 2;i <= n / i;i++) {
				if(x % i == 0) return false;
		}
		
		return true;
}

分解质因数

分解质因数，求底数和指数

暴力求法

void fj(int x) {
		for(int i = 2;i <= n;i++) {
				if(x % i == 0) {
						int s = 0;
						while(x % i == 0) {
								x /= i;
								s++;
						}
						
						cout << i << " " << s << endl;
				}
		}
}

其实和处理质数一样，我们可以通过i <= n / i来缩小时间复杂度，我们每一次while循环对最小质因数进行整除，并且能够保证下一次的质因数一定比这一次while内部的大，如果最终被整除干净的话，x 会变成1

但是如果x是质数的话，我们会发现在2 ~ n - 1这一段区间内并没有数会被整除，最后x还是本身，所以我们最终需要判断x是否为1，如果不是的话，那么我们需要打印x，和指数1

完整Code

#include <bits/stdc++.h>
using namespace std;
void fj(int x) {
    for(int i = 2;i <= x / i;i++) {
        if(x % i == 0) {
                int s = 0;
                while(x % i == 0) {
                        x /= i;
                        s++;
                }

                cout << i << " " << s << endl;
        }
    }

    if(x > 1) cout << x << " " << 1 << endl;
}

int main(){
    int n,t;
    cin >> n;
    while(n--) {
        cin >> t;
        fj(t);
        cout << endl;
    }

    return 0;
}

筛质数

筛选质数的方法即埃氏筛法，主要分为两种筛法形式

朴素筛
线性

朴素筛

在没有任何优化的前提下，进行倍数筛

这种筛法的原理为我们从2开始不断把2的倍数进行标记代表筛过了(这个数一定不是质数)用st数组进行标记，接着再去筛3的倍数，以此类推，最终筛n - 1的倍数，此时st数组已经完善，最终st[i] == 0代表的就是素数

接着我们分析一下时间复杂度

首先我们需要筛选2的倍数 —-> n / 2

接着是3 —– > n / 3 —-> n / 4 ….. n / n

Sn = n / 2 + n / 3 + n / 4 + n / 5 + ... + n / n

n提出来 = n * (1 / 2 + 1 / 3 + 1 / 4 + ...+ 1 / n) = n * (lnn + c) = nlnn < nlog2n 计为 nlogn

Code

void get_prim(int n) {
		for(int i = 2;i <= n;i++) {
				if(st[i]) continue;
				prim[cnt++] = i;
				for(int j = i + i;j <= n;j += i) {
						st[j] = 1;
				}
		}
}

线性筛

线性筛又被称为埃筛，我们主要是通过对质数的倍数进行筛选，同时保证每一个元素被筛一遍，大大减少了时间复杂度

线性筛优化

其实我们可以就计算质数的倍数即可，因为所有的P都是由质因子计算而来的

我们可以计算nlnn中质数的个数，又因为1 ~ n中大约有n / lnn 个质数，所以我们只需要计算n次，即时间复杂度为O(n)

其实这么粗略的计算其实是错误的，答案其实是O(nloglogn)，我们可以简单的看一下loglogn缩小时间的效果

假如n = 2 ^ 32 - > 5 ，和O(n)时间复杂度没有差多少

讲解一下这一道题目的难点

st[primes[j] * i] = true;
if (i % primes[j] == 0) break;

首先分析一下i % primes[j] == 0这一句话

第一种情况i % primes[j] == 0

因为我们for循环是从小到大去遍历所有质因子的，所以如果上述情况成立的话，那么primes[j]一定是i 的最小质因子，并且primes[j]也一定是i * primes[j]的最小质因子

第二种情况i % primes[j] != 0

这种情况primes[j]一定不是i的质因子，准确来说primes[j]没有i的所有质因子大，因为我们是从小到达进行遍历的质因子，同理primes[j]也一定是i * primes[j]的最小质因子

分析完两种我们其实会发现不管是否满足条件，primes[j]为i * primes[j]的最小质因子一定成立

根除法primes[j] <= n / i，正常来看primes[j]代表了最小质因子，我们只需要将小的那一部分的质因子筛选出来，后面的自然会被前面的所覆盖

或者还有一种看法n >= i * primes[j]，我们将n范围内primes[j]素数的倍数进行筛选，我们千万不要这么写，因为当数过大的时候会溢出变成负数

线性优化的原理：保证被自己的最小质因子筛掉

如果还是没有理解的话，我们其实可以举一个例子

假如x = 12

我们尽量系统的分析，不要一步一步分析否则很容易就懵

开始2 是素数放入队列，primes[j]一定为primes[j] * i的最小质因子，进行标记非素数，由于primes[j]是i的最小质因数，我们没有必要往下接着筛，如果想向下进行筛我们是不是要筛6，但是6可以由i = 3 & primes[j] == 2来筛掉，这也正好满足我们的实现原理，保证自己被最小的质因子筛掉，这样就能够避免重复筛一个元素了

接着是3放入队列，上来筛6，此时没有break因为下一个数9必须由i = 3 & primes[j] = 3来筛，否则i = 4之后就筛不了9了，primes[j] == 3 ，筛9，此时需要break，同样后面的12可以由i = 4，primes[j] == 3进行筛掉，

后面也是一样的道理，线性优化，保证唯一性

AC Code

#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;
        }
    }
}

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

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

拭除法求约数

如果n可以被x整除，那么x / n一定也会被x整除，所以说约数也是成对存在的，这个时候我们其实也是可以通过拭除法来解决求约数问题的

Analysis

使用vector集合存约数是因为vector插入和排序都很方便

使用拭除法将一个数约数小的那一面筛选出来的同时将x / 小值也放入到vector集合中

最终排序就可以从小到大获取所有约数

AC Code

#include <bits/stdc++.h>
using namespace std;

vector<int> getYue(int x) {
    vector<int> v;
    for(int i = 1;i <= x / i;i++) {
        if(x % i == 0) {
            if(i == x / i) v.push_back(i);
            else {
                v.push_back(i);
                v.push_back(x / i);
            }
        }
    }

    sort(v.begin(),v.end());
    
    return v;
}


int main(){
    int n;
    cin >> n;
    while(n--) {
        int t;
        cin >> t;
        auto res = getYue(t);

        for(int i = 0;i < res.size();i++) cout << res[i] << " ";
        cout << endl;
    }
    return 0;
}

约数个数

如何求解约数的个数呢？

设N假设N是由约数构成的那么N = p1 ^ u1 + p2 ^ u2 + p3 ^ u3 + ... + pk ^ uk

那么N的约数X一定也是这样构成的X = p1 ^ (0 - u1) + p2 ^ (0 - u2) + ... + pk ^ (0 - uk)

这里面的0 - u1代表的是从0到u1内选值，而不是0 减去 u1

所以约数的个数也就是质数的选值范围P = (u1 + 1)(u2 + 1)(u3 + 1)...(un + 1)

例题：给定 nn 个正整数 aiai，请你输出这些数的乘积的约数个数，答案对 109+7109+7 取模。

思路

其实我们只需要对每一个数的最小公因子的指数进行统计最后套用公式即可

Code

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
typedef long long LL;
int n,t;

unordered_map<int,int> primes;
void getYueNum(int x) {
    for(int i = 2;i <= x / i;i++) {
        while(x % i == 0) { 
            primes[i]++;
            x /= i;
        }

    }

    if(x > 1) primes[x]++;
}


int main(){

    cin >> n;
    LL ans = 1;
    while(n--) {
        cin >> t;
        getYueNum(t);
    }
    
    
    for(auto it : primes) ans = ans * (it.second + 1) % mod;
    
    cout << ans << endl;
    return 0;
}

约数和

想要知道约数和的前提条件一定是要得到每一个数的约数个数。

我们可以简陋的对1 - n之间所有数的约数进行判断

众所周知1是所有数的约数，对应n

2是2的倍数的约数，我们只需要判断1 - n中有多少个2的倍数即可

我们会发现约数之和其实就是找1 - n中包含多少个倍数

我们可以通过上面的发现求解时间复杂度

1的倍数有n个，2的倍数有n / 2个，3的倍数有n / 3个，最终Sn可以写成一个公式

Sn = n + n / 2 + n / 3 + ... + n / n = n * (1 + 1 / 2 + 1 / 3 + ... + 1 / n) = nlogn

约数之和的公式其实可以有约数的个数进行推到

P = (u1 + 1)(u2 + 1)(u3 + 1)...(un + 1)

每一个最小公因数都有自己对应的指数，我们可以对他进行拆解

P1 = (p1 ^ 1 + p1 ^ 2 + p1 ^ 3 + ... + p1 ^ (u1 + 1)) * (p2 ^ 1 + p2 ^ 2 + .. + p2 ^ (u2 + 1)) + ... (pn ^ 1 + ... + pn ^ (un + 1))

约数和和约数个数的本质是一样的也是套用公式

照抄上面的代码

主要关注的细节就是P ^ 0 + p ^ 1 + p ^ 2 + ... + p ^ t如何求解

给出公式sum = sum * P + 1

初始sum = 0，第一步sum = 0 * P + 1 = 1，第二次sum = 1 * P + 1 = P + 1 ，第三次P * (P + 1) + 1 = P ^ 2 + P

最后一定能得到sum = P ^ a + P ^ (a - 1) + ... + 1也就是我们想要的结果

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
typedef long long LL;
int n,t;

unordered_map<int,int> primes;
void getYueNum(int x) {
    for(int i = 2;i <= x / i;i++) {
        while(x % i == 0) { 
            primes[i]++;
            x /= i;
        }

    }

    if(x > 1) primes[x]++;
}


int main(){

    cin >> n;
    LL ans = 1;
    while(n--) {
        cin >> t;
        getYueNum(t);
    }
    
    
    for(auto it : primes) {
      	int p = it.first,a = it.second;
      	LL sum = 1;
      	while(a--) sum = (sum * p + 1) % mod;
      	ans = ans * sum % mod;
    }
    
    cout << ans << endl;
    return 0;
}

欧几里得算法

预先准备：a % b == 0 && a % c == 0 可以推出 a % (bx + cy) == 0

因为a可以被b整除说明a = nb，同理a = mc

将两个等式相加a = nx + mc，n和m是可以取0的。

欧几里得原理：a 和b的最大公约数 = b 和 a % b 的最大公约数

推导过程

a % b 等价于 a - a / b * b

我们把a / b看成一个新数c，即a - c * b，最终只需要判断(a ，b) == (b ，a - c * b)

根据我们上面列举的常识d / a && d / b – > d / ax + by

所以d / a - c * b可以变成d / a - c * b + d / c * b -> d / a

最终就会变成(a，b) == (b，a) ，ab公约数都是相同的

构建求解最大公约数的函数

int gcd(int a,int b) {
		// 如果b是0的话，因为0可以整除任何一个数，所以最大公约数取a
		return b ? gcd(b,a % b) : a;
}