【AcWing】算法基础课-数学知识

1、质数

1.1 试除法判定质数

暴力解法

优化解法

1.2 分解质因数(试除法)

暴力解法

优化解法

1.3 筛质数

朴素筛法(nlogn)

埃氏筛法(nloglogn)

线性筛法(n)

2、约数

2.1 试除法求约数

2.2 约数个数

2.3 约数之和

2.4 最大公约数

实现方法一

实现方法二

3、欧拉函数

3.1 欧拉函数

3.2 筛法求欧拉函数

3.3 欧拉定理、费马定理

4、快速幂

4.1 快速幂

编辑

4.2 快速幂求逆元

1、质数

质数就是在大于1的自然数中，只包含1和本身两个约数的数，也称为素数
合数就是在大于1的自然数中，除了1和本身两个约数，还至少有一个约数的数

1.1 试除法判定质数

866. 试除法判定质数 - AcWing题库

暴力解法

若要判定n是否是质数，暴力解法就是枚举2到n-1之间所有的数，看n能否整除这些数

#include<iostream>
using namespace std;bool is_prime(int n)
{if(n < 2) return false;for(int i = 2;i < n;i ++)if(n % i == 0) return false;return true;
}int main()
{int n; cin >> n;while(n --){int a; cin >> a;if(is_prime(a)) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}

此时是会超时的。is_prime的时间复杂度是O(n)。

优化解法

我们可以对上面的is_prime进行优化。我们会发现，若d能够整除n，则n/d也能够整除n。例如当n=12时，3能够整除12，同样12/3=4也能够整除12。也就是说，约数是成对出现的。所以，我们可以利用这个性质，枚举时只枚举较小的哪一个约数即可。两个约数一个是d，另一个是n/d，假设d较小d <= n/d，计算出来d <= sqrt(n)，所以这种算法的时间复杂度是O(sqrt(n))

#include<iostream>
using namespace std;bool is_prime(int n)
{if(n < 2) return false;for(int i = 2;i <= n / i;i ++)if(n % i == 0) return false;return true;
}int main()
{int n; cin >> n;while(n --){int a; cin >> a;if(is_prime(a)) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}

注意：上面的i <= n / i表示的是只枚举较小的哪一个约数(i <= sqrt(n))，此时可能会有下面另外两种写法
(1) i <= sqrt(n)，是不推荐的，因为sqrt函数较慢
(2) i * i <= n，同样不推荐，可能会造成溢出

1.2 分解质因数(试除法)

867. 分解质因数 - AcWing题库

暴力解法

若要分解n的质因数，暴力解法就是就是枚举2到n的所有数，若这其中的某一个数能够整除n，说明这个数就是n的一个质因数

#include<iostream>
using namespace std;void divide(int n)
{for(int i = 2;i <= n;i ++){if(n % i == 0){int s = 0;while(n % i == 0){n /= i;s ++;}cout << i << " " << s << endl;}}cout << endl;
}int main()
{int n; cin >> n;while(n --){int a; cin >> a;divide(a);}return 0;
}

此时可能会有一个疑问，就是我们要的是质因数，不需要先判断以下i是否是质数吗？是不需要的，因为当枚举到i时，已经将2-i-1之间所有的质因子除干净了，所以当n%i==0成立，则i一定是质数。例如100，4是其约数，但4是一个合数，当i枚举到4时，一定会先遇到4的约数，即2，所以i到4时，4已经不是25的约数了

上面的代码时会超时的，当n是质数时，达到最坏时间复杂度O(n)

优化解法

我们会发现，n的质因子中，最多只能有一个是大于sqrt(n)的，所以我们可以先将<=sqrt(n)的所有质因子先找出来，若最后n>1，则n就是那个大于sqrt(n)的质因子，这样的时间复杂度是O(sqrt(n))

#include<iostream>
using namespace std;void divide(int n)
{for(int i = 2;i <= n / i;i ++){if(n % i == 0){int s = 0;while(n % i == 0){n /= i;s ++;}cout << i << " " << s << endl;}}if(n > 1) cout << n << " " << 1 << endl;cout << endl;
}int main()
{int n; cin >> n;while(n --){int a; cin >> a;divide(a);}return 0;
}

在这两道题中，质数判定的时间复杂度一定是O(sqrt(n))的，但分解质因数不一定，当n = 2^k时，达到最好时间复杂度O(logn)，所以时间复杂度是在O(logn)~O(sqrt(n))的

1.3 筛质数

868. 筛质数 - AcWing题库

朴素筛法(nlogn)

对于n，朴素筛法是从前向后遍历2到n之间的所有数，每次遍历到一个数时，就将其在n范围内的倍数都删除，若第一次遍历到这个数是没有被删除的，说明这个数就是质数。假设p没有被删除，说明p不是2到p-1之间如何一个数的倍数，即p是质数

#include<iostream>
using namespace std;const int N = 1e6 + 10;int cnt;
bool st[N];void get_primes(int n)
{for(int i = 2;i <= n;i ++){if(!st[i]) cnt ++; // 第一次遍历到这个数没有被删除，则这个数就是质数for(int j = i + i;j <= n;j += i) st[j] = true; // 删除倍数}
}int main()
{int n; cin >> n;get_primes(n);cout << cnt << endl;return 0;
}

这个筛法的时间复杂度是O(nlogn)的，在get_primes中，当i等于2时，向后删除倍数是循环n/2次，当i等于3时，向后删除倍数是循环n/3次，...，当i等于n时，向后删除倍数是循环n/n次。所以get_primes总的循环次数就是(n/2 + n/3 + ... + n/n)，大约是等于O(nlogn)的

埃氏筛法(nloglogn)

在上面的get_primes中，不管i是否是质数，我们都删除它的倍数，实际上只有当i是质数时，我们才需要删除。因为遍历到合数时，这个合数一定有比本身更小的质因子，此时这个合数已经被删掉了，并且这个合数的所有倍数也一定含有这个质因子，所以合数的所有倍数都已经被删掉了，再去删除其倍数是没有意义的。

#include<iostream>
using namespace std;const int N = 1e6 + 10;int cnt;
bool st[N];void get_primes(int n)
{for(int i = 2;i <= n;i ++){if(!st[i]) {cnt ++; // 第一次遍历到这个数没有被删除，则这个数就是质数for(int j = i + i;j <= n;j += i) st[j] = true; // 删除倍数}}
}int main()
{int n; cin >> n;get_primes(n);cout << cnt << endl;return 0;
}

这个算法实际上就是每个合数使用它的质因子筛掉。时间复杂度是O(nloglogn)

埃氏筛法，对于每一个合数，它的每一个质因子都会将这个合数删除一遍，所以时间复杂度无法达到O(n)，若每个合数只会被其中一个质因子删除，那么就达到了O(n)

线性筛法(n)

线性筛法是每一个合数，只会由这个合数的最小质因子删除，所以每一个合数只会被删除一次，时间复杂度就是O(n)。线性筛法是筛的时候，从小到大遍历当前得到的所有质数，每次将当前质数与i的乘积删掉。每次删掉一个数时，是用其最小质因子删掉的。primes数组是存放已筛出的质数的

primes[j] * i一定是合数。当if (i % primes[j] == 0)这个条件是为了保证每一个合数只会被它的最小质因子删除。
（1）当i%primes[j] != 0时，primes[j]一定小于i的所有质因子，primes[j]也一定是primes[j]*i的最小质因子
（2）当i%primes[j] == 0时，primes[j]一定等于i的最小质因子，primes[j]也一定是primes[j]*i的最小质因子
例如i = 9，primes[j] = 3，此时会删除27，但不能再向后删除了，因为下一个primes[j] = 5，若将45删除，45的最小质因子不是5，是3，此时若删除了，等到i = 15，primes[j] = 3时还会再删除一次，就无法保证每一个合数只会被它的最小质因子删除。

#include<iostream>
using namespace std;const int N = 1e6 + 10;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;
}

2、约数

约数是指能够整除一个整数的所有整数。换句话说，如果整数 a 除以整数 b 后得到的商是一个整数，并且没有余数，那么 b 就是 a 的约数。例如6的约数有1，2，3，6

2.1 试除法求约数

869. 试除法求约数 - AcWing题库

在前面已经提到过约数是成对出现的，对于n，若d是它的约数，那么n/d也是它的约数。所以我们求约数只枚举小的一半即可，然后通过n/d获取另一个约数

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;vector<int> get_divisors(int x)
{vector<int> res;for (int i = 1; i <= x / i; i ++ )if (x % i == 0){res.push_back(i);if (i != x / i) res.push_back(x / i); // 一定要有这一步，因为当i == x / i时只需要加入一个即可}sort(res.begin(), res.end());return res;
}int main()
{int n;cin >> n;while (n -- ){int x;cin >> x;auto res = get_divisors(x);for (auto x : res) cout << x << ' ';cout << endl;}return 0;
}

2.2 约数个数

870. 约数个数 - AcWing题库

对于任何一个数，都可以分解成由质因子相乘的结果。假设n的所有质因数为n1,n2,...,nk

n的约数个数 = (a1 + 1)(a2 + 1)...(ak + 1)

例如n = 360，质因子为2，3，5，360 = 2^3 + 3^2 + 5^1，所以对于2^x + 3^y + 5^z，在这其中x取0到3，y取0到2，z取0到1都是n的约数，所以约数个数 = 4 * 3 * 2 = 24

所以在求一个数的约数个数之前，需要先将这个数进行质因数分解。在这道题中我们要求的是a1 * a2 * ... * an的约数个数，我们可以分别求出每一个数的约数个数，然后再相加。

#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] ++ ;}// 将每一个质因数的次方+1再相乘LL res = 1;for (auto p : primes) res = res * (p.second + 1) % mod;cout << res << endl;return 0;
}

2.3 约数之和

871. 约数之和 - AcWing题库

在上面我们已经将一个数n分解成了质因数相乘的形式

约数之和等于

#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;res = res * t % mod;}cout << res << endl;return 0;
}

2.4 最大公约数

872. 最大公约数 - AcWing题库

使用欧几里得算法，也称为辗转相除法

实现方法一

我们可以将上一次的除数作为下一次的被除数，上一次的余数作为下一次的除数，直到余数为0，此时的除数就是最大公约数

#include<iostream>
using namespace std;int Fac(int a, int b)
{int c = 1; // c用来保存余数while (c){c = a % b;a = b; // a是被除数b = c; // b是除数}return a;
}int main()
{int n; cin >> n;while(n --){int a, b; cin >> a >> b;cout << Fac(a, b) << endl;}return 0;
}

实现方法二

#include <iostream>
#include <algorithm>using namespace std;int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n; cin >> n;while (n -- ){int a, b; cin >> a >> b;cout << gcd(a, b) << endl;}return 0;
}

3、欧拉函数

3.1 欧拉函数

873. 欧拉函数 - AcWing题库

#include <iostream>using namespace std;int phi(int x)
{int res = x;for (int i = 2; i <= x / i; i ++ )if (x % i == 0) // 如果i是x的质因数{res = res - res / i;while (x % i == 0) x /= i; // 将i除干净}if (x > 1) res = res / x * (x - 1); // 可能会有一个大于sqrt(n)的质因数return res;
}int main()
{int n;cin >> n;while (n -- ){int x;cin >> x;cout << phi(x) << endl;}return 0;
}

这里为了能够整除，不能res = res * (1 - 1 / i)，而需要res = res - res * i
时间复杂度是O(n * sqrt(a))，并且这个时间复杂度是一定这样的

3.2 筛法求欧拉函数

874. 筛法求欧拉函数 - AcWing题库

这道题是要求1-n所有数的欧拉函数之和，若使用上面从定义出发的做法，时间复杂度是
O(n * sqrt(n))，对于这一道题的数据是会超时的。此时可以使用前面线性筛法求质数的方法，在线性筛法的过程中，顺便求出欧拉函数。时间复杂度是O(n)

#include <iostream>using namespace std;typedef long long LL;const int N = 1000010;int primes[N], cnt;
int euler[N]; // 存放每一个数的欧拉函数
bool st[N];void get_eulers(int n)
{euler[1] = 1;for (int i = 2; i <= n; i ++ ){if (!st[i]){primes[cnt ++ ] = i;euler[i] = i - 1;}for (int j = 0; primes[j] <= n / i; j ++ ){int t = primes[j] * i;st[t] = true;if (i % primes[j] == 0){euler[t] = euler[i] * primes[j];break;}euler[t] = euler[i] * (primes[j] - 1);}}
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n; cin >> n;get_eulers(n);LL res = 0;for (int i = 1; i <= n; i ++ ) res += euler[i];cout << res << endl;return 0;
}

欧拉函数之和可能会超过int，所以要开long long

3.3 欧拉定理、费马定理

4、快速幂

4.1 快速幂

875. 快速幂 - AcWing题库

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;LL qmi(int a, int b, int p)
{LL res = 1 % p;while (b){if (b & 1) res = res * a % p; // 这一步成立说明末位是1a = a * (LL)a % p;b >>= 1;}return res;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n; cin >> n;while (n -- ){int a, b, p; cin >> a >> b >> p;cout << qmi(a, b, p) << endl;}return 0;
}

两个10^9相乘，所以要开long long

4.2 快速幂求逆元

876. 快速幂求逆元 - AcWing题库

#include <iostream>
#include <algorithm>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 = a * (LL)a % p;b >>= 1;}return res;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n; cin >> n;while (n -- ){int a, p; cin >> a >> p;if (a % p == 0) cout << "impossible" << endl;else cout << qmi(a, p - 2, p) << endl;}return 0;
}