4. 数学知识（I）
4.1 质数
4.1.1 试除法判定质数
题目：给你 \(n\) 个正整数 \(a_i\)，判断其是否是质数。\(1\le n\le 100,1\le a_i\le 2^{31}-1\)。
思路：
根据质数的定义，可知若 \(2\sim a-1\) 之间的数都不能整除 \(a\)，则 \(a\) 为质数。那么遍历 \(2\sim a-1\) 之间的数，判断其能否整除 \(a\) 即可，时间复杂度 \(O(a)\)。
考虑优化。我们知道，若 \(p\mid a\)，则 \(\dfrac{a}{p}\mid a\)。所以我们可以只遍历 \(2\sim \sqrt{a}\) 之间的数即可。时间复杂度 \(O\left(n\sqrt{a}\right)\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
bool prime(int x) { // 判断x是否是质数
if (x == 1) return 0; // 1既不是质数,也不是合数
for (int i = 2; i <= x/i; ++i) // i<=n/i即i*i<=m
if (x % i == 0) return 0;
return 1; // 如果x不能被2~sqrt(x)之间的数整除,说明x是质数
}
int main() {
scanf("%d", &n);
while (n -- ) {
int x;
scanf("%d", &x);
if (prime(x)) puts("Yes");
else puts("No");
}
return 0;
}
4.1.2 分解质因数
题目：给你 \(n\) 个整数 \(a_i\)，将其分解质因数，并按照质因子从小到大的顺序输出每个质因子的底数和指数。\(1\le n\le 100,2\le a_i\le 2\times 10^9\)。
思路：
与试除法类似地，我们枚举 \(i\in[2,\sqrt{a}]\)，若 \(i\mid a\) 则不断将 \(a\) 除以 \(i\)，直到 \(i\not\mid a\) 为止，同时用一个计数器 \(cnt\) 记录除的次数。那么 \(i\) 的质数即为 \(cnt\)，显然这样的 \(i\) 都是质数。最后若 \(a>1\)，说明 \(a\) 有一个大于 \(\sqrt{a}\) 的质因子，指数为 \(1\)，直接输出即可。
时间复杂度 \(O(n\sqrt{a})\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, x;
int main() {
scanf("%d", &n);
while (n -- ) {
scanf("%d", &x);
for (int i = 2; i <= x/i; ++i) {
if (x % i == 0) {
int cnt = 0;
while (x % i == 0) cnt ++, x /= i;
printf("%d %d\n", i, cnt);
}
}
if (x != 1) printf("%d 1\n", x);
puts("");
}
return 0;
}
4.1.3 筛质数
题目：给你一个数 \(n\)，计算 \([1,n]\) 中质数的数量。\(1\le n\le 10^6\)。
4.1.3.1 埃氏筛
思路：
最朴素的埃氏筛出于这样的想法：我们从 \(2\) 开始枚举每一个数，用 \(st_i\) 存储数 \(i\) 是否被打上标记。若遍历到 \(i\) 时 \(st_i=0\)，说明 \(i\) 是质数，将其加入质数数组 \(prime\) 中；反之则说明 \(i\) 不是质数。接着我们枚举 \(i\) 的倍数，将它们都打上标记。
朴素的埃氏筛时间复杂度为 \(O(n\log n)\)。
我们考虑优化。由于一个合数的倍数必定被其质因子筛过了，所以我们只需要筛质数的倍数即可。时间复杂度 \(O(n\log \log n)\)。
核心代码：
int n;
int prime[N], cnt;
bool st[N];
void Eratosthenes(int n) {
st[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!st[i]) {
prime[++cnt] = i;
for (int j = i+i; j <= n; j += i) st[j] = 1;
}
}
}
4.1.3.2 线性筛
思路：
尽管改进版的埃氏筛已经很快了，但其仍然存在一个问题：例如，对于 \(15\)，\(3\) 会筛掉它，\(5\) 也会筛掉它，这样就造成了时间浪费。对于数 \(i\)，我们从第 \(1\) 个质数 \(2\) 开始循环，筛去质数与 \(i\) 的乘积。直到 \(i\bmod prime_j=0\) 时或 \(prime_j>n/i\) 时跳出。
由于每个数只会被筛一次，所以时间复杂度为 \(O(n)\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int n;
int prime[N], cnt;
bool st[N];
void Euler(int n) {
st[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!st[i]) prime[++cnt] = i;
for (int j = 1; j <= cnt && prime[j] <= n/i; ++j) {
st[i*prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
int main() {
scanf("%d", &n);
Euler(n);
printf("%d\n", cnt);
return 0;
}
4.2 约数
4.2.1 试除法求约数
题目：给你 \(n\) 个整数 \(a_i\)，计算每个数的约数，按从小到大的顺序输出。\(1\le n\le 100,2\le a_i\le 2\times 10^9\)。
思路：基本和试除法的思路是相同的。我们用一个数组 \(fac\) 来存储 \(a_i\) 的因数。从 \(2\) 开始遍历到 \(\sqrt{a_i}\)，再倒序遍历 \(fac\) 输出 \(a_i/fac_i\) 即可。注意特判完全平方数。
时间复杂度 \(O(n\sqrt{a_i})\)
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5e4+10;
int n, x;
int fac[N], idx;
int main() {
scanf("%d", &n);
while (n -- ) {
scanf("%d", &x); idx = 0;
for (int i = 1; i <= x/i; ++i) {
if (x % i == 0)
fac[++idx] = i, printf("%d ", i);
}
if ((long long)fac[idx]*fac[idx] == x) idx --;
for (int i = idx; i >= 1; --i) printf("%d ", x/fac[i]);
puts("");
}
return 0;
}
4.2.2 约数个数
题目：给定 \(n\) 个正整数 \(a_i\)，计算 \(\prod a_i\) 的约数个数对 \(10^9+7\) 取模的值。\(1\le n\le 100,1\le a_i\le 2\times 10^9\)。
思路：
我们约定：\(\mathbb{P}\) 表示质数集。
考虑一个数 \(x\)，假设其质因数分解后得到的乘积为：
\[x=\prod_{i=1}^m p_i^{r_i}\tag{4.1} \]其中，\(p_i\in\mathbb{P}\)，\(r_i\in\mathbb{N}_+\)，且 \(p_1<p_2<\cdots<p_m\)。
对于 \(x\) 的质因子 \(p_i\)，都有选 \(0\) 个，选 \(1\) 个，……选 \(r_i\) 个共 \(r_i+1\) 种选择。 由乘法原理，\(x\) 的质因数个数即为：
\[\prod_{i=1}^m(r_i+1)\tag{4.2} \]在本题中，我们对于每个 \(a_i\) 先分解好质因数，最后乘起来即可。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int P = 1e9+7;
unordered_map<int, int> p;
int n, x, ans = 1;
int main() {
scanf("%d", &n);
while (n -- ) {
scanf("%d", &x);
for (int i = 2; i <= x/i; ++i) {
while (x % i == 0)
x /= i, p[i] ++;
}
if (x > 1) p[x] ++;
}
for (auto i : p) ans = (ll)ans * (i.second + 1) % P;
printf("%d\n", ans);
return 0;
}
4.2.3 约数之和
题目：给定 \(n\) 个正整数 \(a_i\)，计算 \(\prod a_i\) 的约数之和对 \(10^9+7\) 取模的值。\(1\le n\le 100,1\le a_i\le 2\times 10^9\)。
思路：类似 4.2.2 中的思路。考虑一个数 \(x\)，假设其质因数分解后得到的乘积为：
\[x=\prod_{i=1}^m p_i^{r_i}\tag{4.3} \]其中，\(p_i\in\mathbb{P}\)，\(r_i\in\mathbb{N}_+\)，且 \(p_1<p_2<\cdots<p_m\)。
由乘法原理，其约数之和为：
\[\prod_{i=1}^m\sum_{j=0}^{r_i} p_i^j\tag{4.4} \]代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int mod = 1e9+7;
typedef long long ll;
unordered_map<int, int> p;
int n, x, ans = 1;
int main() {
scanf("%d", &n);
while (n -- ) {
scanf("%d", &x);
for (int i = 2; i <= x/i; ++i) {
while (x % i == 0)
x /= i, p[i] ++;
}
if (x > 1) p[x] ++;
}
for (auto t : p) {
int pr = t.first, num = t.second, tmp = 1;
while (num -- ) tmp = ((ll)tmp * pr + 1) % mod;
ans = (ll)ans * tmp % mod;
}
printf("%d\n", ans);
return 0;
}
4.2.4 最大公约数（GCD）
定义：
若自然数 \(d\) 同时是自然数 \(a,b\) 的约数，则称 \(d\) 为 \(a,b\) 的公约数。在所有 \(a,b\) 的公约数中最大的一个，称为 \(a,b\) 的最大公约数，记作 \(\gcd(a,b)\)。
若自然数 \(m\) 同时是自然数 \(a,b\) 的倍数，则称 \(m\) 为 \(a,b\) 的公倍数。在所有 \(a,b\) 的公倍数中最小的一个，称为 \(a,b\) 的最小公倍数，记作 \(\text{lcm}(a,b)\)。
同理，我们也可以定义多个数的最大公约数和最小公倍数。
题目：给定 \(n\) 个数对 \(a_i,b_i\)，计算 \(\gcd(a_i,b_i)\)。\(1\le n\le 10^5,1\le a_i,b_i\le 2\times 10^9\)。
思路：
九章算术·更相减损术：
\[\begin{aligned} & \forall a,b\in\mathbb{N},a\ge b,\; \gcd(a,b) = \gcd(b,a-b)\\ \end{aligned} \]证明：
对于 \(a,b\) 的任意公约数 \(d\)，由于 \(d\mid a,d\mid b\)，所以 \(d\mid a-b\)，因此 \(d\) 也是 \(b,a-b\) 的公约数。故 \(a,b\) 的公约数集合与 \(b,a-b\) 的公约数集合相同，因此它们的最大公约数也相同。
证毕。
欧几里得算法：
\[\begin{aligned} & \forall a,b\in\mathbb{N},b\ne 0,\; \gcd(a,b) = \gcd(b,a\bmod b)\\ \end{aligned} \]证明：
当 \(a<b\) 时，\(a\bmod b=a\)，命题成立。
当 \(a\ge b\) 时，不妨设 \(a=q\times b+r\)，其中 \(q,r\in\mathbb{N},0\le r<b\)，则 \(a\bmod b=r\)。对于 \(a,b\) 的任意公约数 \(d\)，由于 \(d\mid a,d\mid q\times b\)。所以 \(d\mid (a-qb)\)，即 \(d\mid r\)，因此 \(d\) 也是 \(b,a\bmod b\) 的公约数。 \(a,b\) 的公约数集合与 \(b,a\bmod b\) 的公约数集合相同，因此它们的最大公约数也相同。 命题成立。
证毕。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, a, b;
int gcd(int a, int b) {
if (!b) return a;
return gcd(b, a%b);
}
int main() {
scanf("%d", &n);
while (n -- ) {
scanf("%d%d", &a, &b);
printf("%d\n", gcd(a, b));
}
return 0;
}
4.3 欧拉函数
定义：
\(\forall a,b\in\mathbb{N}\)，若 \(\gcd(a,b)=1\)，则称 \(a,b\) 互质。同理，若 \(\gcd(a,b,c)=1\)，则称 \(a,b,c\) 互质。若 \(\gcd(a,b)=\gcd(a,c)=\gcd(b,c)\) 称为 \(a,b,c\) 两两互质。后者显然是一个更强的条件。
欧拉函数：
\(1\sim n\) 中与 \(n\) 互质的数的个数称为欧拉函数，记作 \(\varphi(n)\)。若在算数基本定理中，\(n=\prod_{i=1}^mp_i^{r_i}\)，则：
\[\varphi(n)=n\times\prod_{i=1}^m\left(1-\dfrac{1}{p_i}\right)\tag{4.5} \]证明：
设 \(p\) 是 \(n\) 的质因子，则 \([1,n]\) 中 \(p\) 的倍数有 \(p,2p,3p,\cdots,(n/p)\times p\)，共 \(\dfrac{n}{p}\) 个。同理，若 \(q\) 也是 \(n\) 的质因子，则 \([1,n]\) 中 \(q\) 的倍数有 \(\dfrac n q\) 个。如果我们将这 \(\left(\dfrac n p+\dfrac n q\right)\) 个数去掉，则 \(pq\) 的倍数都被排除了两次，需要加回来一次。因此，\([1,n]\) 中不包含质因子 \(p,q\) 的数的个数为：
\[n-\left(\dfrac n p+\dfrac n q-\dfrac n {pq}\right)=n\left(1-\dfrac 1 p -\dfrac 1 q+\dfrac 1 {pq}\right)=n\left(1-\dfrac 1 p\right)\left(1-\dfrac 1 q\right)\tag{4.6} \]类似地，对 \(n\) 的所有质因数使用容斥原理，即可得到 \((4.5)\)。
证毕。
4.3.1 分解质因数求欧拉函数
题目：给定 \(n\) 个正整数 \(a_i\)，计算 \(\varphi(a_i)\)。\(1\le n\le 100,1\le a_i\le 2\times 10^9\)。
思路：根据欧拉函数的计算方式，可以将 \(a_i\) 分解质因数计算 \(\varphi(a_i)\)。时间复杂度 \(O(n\sqrt{a_i})\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, x;
int get_euler(int x) {
int ans = x;
for (int i = 2; i <= x/i; ++i) {
bool check = 0;
while (x % i == 0) {
x /= i;
check = 1;
}
if (check) ans = ans / i * (i-1);
}
if (x > 1) ans = ans / x * (x-1);
return ans;
}
int main() {
scanf("%d", &n);
while (n -- ) {
scanf("%d", &x);
int ans = get_euler(x);
printf("%d\n", ans);
}
return 0;
}
4.3.2 埃氏筛求欧拉函数
未完待续……
标签：le,int,dfrac,质数,ans,数学知识,include From： https://www.cnblogs.com/Jasper08/p/16946074.html