数学专题3 - 质因数分解

1. 质因数分解

1.1 质因数分解的定义

质因数分解是将一个正整数表示为几个质数的乘积的过程。每个大于1的整数都可以唯一地分解为质数的乘积。

1.2 质因数分解的方法

1.2.1 试除法

试除法是通过逐个试除小于等于该数平方根的质数来寻找质因数的方法。

1.2.1.1天秀的数列挑战

天秀面前有一个长度为 ( n ) 的数列 ( A )，每个元素是正整数。她可以进行多次操作，每次操作选择数列中的一个元素并将其替换为其任意质因数（也可以是它本身）。

现在，天秀想知道，至少需要多少次操作，才能使数列中的所有元素相等。

输入格式

第一行包含一个整数 ( n )（( 1 \leq n \leq 10^5 )）。

第二行包含 ( n ) 个整数，表示数列 ( A )，其中 ( 1 \leq A[i] \leq 10^7 )。

输出格式

输出一个整数，表示最少的操作次数。

样例输入1

3
4 6 8

样例输出1

2

样例解释1

一个可能的操作序列是：( 6 ) 变为 ( 3 )，( 8 ) 变为 ( 4 )，然后 ( 4 ) 和 ( 3 ) 都变为 ( 1 )。

样例输入2

4
10 14 22 35

样例输出2

3

样例解释2

所有数都可以通过至多3次操作变为1，例如 ( 10 ) 变为 ( 5 )，( 14 ) 和 ( 22 ) 变为 ( 11 )，( 35 ) 变为 ( 7 )，最后这些质数都变为 ( 1 )。

样例输入3

2
15 25

样例输出3

1

样例解释3

( 25 ) 可以直接变为 ( 5 )，然后 ( 15 ) 和 ( 5 ) 都变为 ( 5 )。

样例输入4

5
2 4 8 16 32

样例输出4

4

样例解释4

这是2的幂次数列，最优操作是逐步降低每个数的幂次。

样例输入5

3
17 34 51

样例输出5

1

样例解释5

所有数字都可以变为17。

数据范围

• 对于 $30\%$ 的数据，( n \leq 100 )，( A[i] \leq 1000 )。
• 对于 $100\%$ 的数据，( 1 \leq n \leq 10^5 )，( 1 \leq A[i] \leq 10^7 )。

解题思路

这是一个关于质因数分解的问题。需要高效地对数列中的每个数进行质因数分解，然后找出使所有数相等的最小操作次数。直接的暴力方法由于数据范围很大往往不能通过，需要采用更高效的算法来处理质因数分解，比如使用埃拉托斯特尼筛法或欧拉筛法预处理质数，并快速分解数列中的数。
这里是上述代码的中文注释版本：

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>using namespace std;const int MAXN = 10000000;  // 最大范围设为10^7
vector<int> primes;  // 用于存储所有质数
vector<bool> is_prime(MAXN + 1, true);  // 标记是否为质数// 埃拉托斯特尼筛法
void sieve() {is_prime[0] = is_prime[1] = false;  // 0和1不是质数for (int i = 2; i * i <= MAXN; ++i) {if (is_prime[i]) {primes.push_back(i);for (int j = i * i; j <= MAXN; j += i) {is_prime[j] = false;  // 剔除i的倍数}}}
}// 解决问题的主要函数
int solve(const vector<int>& nums) {map<int, int> factor_count;  // 存储每个质因数出现的次数for (int num : nums) {for (int prime : primes) {if (prime * prime > num) break;  // 超过范围则停止while (num % prime == 0) {  // 除尽所有质因数factor_count[prime]++;num /= prime;}}if (num > 1) factor_count[num]++;  // 处理剩余的大于1的数}int max_operations = 0;  // 最大操作次数for (auto& p : factor_count) {max_operations = max(max_operations, p.second);  // 找出最大频次}return max_operations;
}int main() {int n;cin >> n;  // 输入数列长度vector<int> nums(n);  // 存储数列for (int i = 0; i < n; ++i) {cin >> nums[i];  // 输入数列各元素}sieve();  // 预处理质数cout << solve(nums) << endl;  // 输出最小操作次数return 0;
}

这个程序使用埃拉托斯特尼筛法来预处理质数，并用它们来分解数列中的每个数，同时统计每个质因数出现的次数。最后，计算出使所有数相等所需的最少操作次数。

1.2.1.2 天秀的跑道赛

天秀是一名运动员，她正在参加一个特别的跑道赛。这个赛道有多条跑道，每条跑道的长度不同，运动员需要在每条跑道上跑整数圈才能完成比赛。天秀想要知道，为了在所有跑道上跑相同的总距离，她至少需要跑多少距离。

输入格式

第一行包含一个整数 ( n )（( 1 \leq n \leq 10^3 )），表示跑道的数量。

第二行包含 ( n ) 个整数，每个整数 ( L_i )（( 1 \leq L_i \leq 10^3 )）表示每条跑道的长度（单位：米）。

输出格式

输出一个整数，表示天秀为了在每条跑道上至少跑一圈且总距离相同，至少需要跑的总距离（单位：米）。

样例输入1

3
400 300 600

样例输出1

1200

样例解释1

天秀可以在第一条跑道上跑3圈（1200米），第二条跑道上跑4圈（1200米），第三条跑道上跑2圈（1200米），使得在每条跑道上的跑行距离都是1200米。

样例输入2

2
200 450

样例输出2

1800

样例解释2

天秀可以在第一条跑道上跑9圈（1800米），第二条跑道上跑4圈（1800米），使得在两条跑道上的跑行距离都是1800米。

解题思路

这个问题实际上是在求多个数的最小公倍数，但是我们可以通过模拟的方式来表述这个问题。在赛道长度的背景下，求最小公倍数实际上就是找出可以让天秀在所有跑道上至少跑一圈的最短总距离。

以下是这个问题的C++解答：

#include <iostream>
#include <vector>
using namespace std;// 计算最大公约数
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}// 计算最小公倍数
int lcm(int a, int b) {return a / gcd(a, b) * b;
}int main() {int n;cin >> n;vector<int> tracks(n);for (int i = 0; i < n; ++i) {cin >> tracks[i];}int result = tracks[0];for (int i = 1; i < n; ++i) {result = lcm(result, tracks[i]);}cout << result << endl;return 0;
}

这段代码通过模拟天秀在跑道上跑步的过程，计算她需要跑的最短总距离，实际上就是求解了所有跑道长度的最小公倍数。天秀的跑道赛

天秀是一名运动员，她正在参加一个特别的跑道赛。这个赛道有多条跑道，每条跑道的长度不同，运动员需要在每条跑道上跑整数圈才能完成比赛。天秀想要知道，为了在所有跑道上跑相同的总距离，她至少需要跑多少距离。

输入格式

第一行包含一个整数 ( n )（( 1 \leq n \leq 10^3 )），表示跑道的数量。

第二行包含 ( n ) 个整数，每个整数 ( L_i )（( 1 \leq L_i \leq 10^3 )）表示每条跑道的长度（单位：米）。

输出格式

输出一个整数，表示天秀为了在每条跑道上至少跑一圈且总距离相同，至少需要跑的总距离（单位：米）。

样例输入1

3
400 300 600

样例输出1

1200

样例解释1

天秀可以在第一条跑道上跑3圈（1200米），第二条跑道上跑4圈（1200米），第三条跑道上跑2圈（1200米），使得在每条跑道上的跑行距离都是1200米。

样例输入2

2
200 450

样例输出2

1800

样例解释2

天秀可以在第一条跑道上跑9圈（1800米），第二条跑道上跑4圈（1800米），使得在两条跑道上的跑行距离都是1800米。

解题思路

这个问题实际上是在求多个数的最小公倍数，但是我们可以通过模拟的方式来表述这个问题。在赛道长度的背景下，求最小公倍数实际上就是找出可以让天秀在所有跑道上至少跑一圈的最短总距离。

以下是这个问题的C++解答：

#include <iostream>
#include <vector>
using namespace std;// 计算最大公约数
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}// 计算最小公倍数
int lcm(int a, int b) {return a / gcd(a, b) * b;
}int main() {int n;cin >> n;vector<int> tracks(n);for (int i = 0; i < n; ++i) {cin >> tracks[i];}int result = tracks[0];for (int i = 1; i < n; ++i) {result = lcm(result, tracks[i]);}cout << result << endl;return 0;
}

这段代码通过模拟天秀在跑道上跑步的过程，计算她需要跑的最短总距离，实际上就是求解了所有跑道长度的最小公倍数。

1.2.1.3 天秀的数字游戏

天秀在玩一个数字游戏。游戏规则是：给定一个正整数区间 ([L, R])，天秀需要找出这个区间内每个数的质因数分解，并计算出所有这些数的质因数分解中质因数的总数量。

输入格式

输入包含两个整数 ( L ) 和 ( R )（( 1 \leq L \leq R \leq 10^6 )）。

输出格式

输出一个整数，表示区间 ([L, R]) 内所有数的质因数分解中质因数的总数量。

样例输入1

2 5

样例输出1

4

样例解释1

• 2 的质因数是 2。
• 3 的质因数是 3。
• 4 的质因数是 2, 2。
• 5 的质因数是 5。

所以，质因数的总数量是 4。

样例输入2

6 10

样例输出2

7

样例解释2

• 6 的质因数是 2, 3。
• 7 的质因数是 7。
• 8 的质因数是 2, 2, 2。
• 9 的质因数是 3, 3。
• 10 的质因数是 2, 5。

所以，质因数的总数量是 7。

解题思路

对于这个问题，暴力地为区间内每个数进行质因数分解是不现实的，因为当区间很大时，这样做的时间复杂度非常高。可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）或欧拉筛法来高效地找出所有需要的质数，并进行质因数分解。

以下是采用欧拉筛法的C++解答：

#include <iostream>
#include <vector>using namespace std;const int MAXN = 1000000;
vector<int> primes;
vector<bool> is_prime(MAXN + 1, true);// 欧拉筛法
void eulerSieve(int n) {for (int i = 2; i <= n; ++i) {if (is_prime[i]) {primes.push_back(i);}for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {is_prime[i * primes[j]] = false;if (i % primes[j] == 0) break;}}
}// 计算区间内所有数的质因数总数量
int countPrimeFactors(int L, int R) {eulerSieve(R);int total = 0;for (int i = L; i <= R; ++i) {int n = i;for (int prime : primes) {if (prime * prime > n) break;while (n % prime == 0) {total++;n /= prime;}}if (n > 1) total++;  // n 自身是一个质数}return total;
}int main() {int L, R;cin >> L >> R;cout << countPrimeFactors(L, R) << endl;return 0;
}

这个解法中，eulerSieve 函数使用欧拉筛法生成所有需要的质数，并存储在 primes 数组中。然后 countPrimeFactors 函数计算区间 [L, R] 内每个数的质因数分解中质因数的总数量。这种方法的时间复杂度相对较低，适合处理大范围的数据。

题目：天秀的秘密数字

天秀正在参与一个解密游戏，她需要找到一个特定的秘密数字。这个秘密数字是在一个给定区间 ([L, R]) 内唯一一个满足以下条件的整数：它的质因数分解中恰好有 ( K ) 个不同的质因数。

输入格式

输入包含三个整数 ( L ), ( R ) 和 ( K )（( 1 \leq L \leq R \leq 10^6 )，( 1 \leq K \leq 10 )）。

输出格式

输出一个整数，表示区间 ([L, R]) 内满足条件的秘密数字。如果不存在这样的数字，则输出 -1。

样例输入1

2 10 2

样例输出1

6

样例解释1

在区间 ([2, 10]) 内，( 6 = 2 \times 3 ) 有 2 个不同的质因数，满足条件。

样例输入2

10 20 3

样例输出2

30

样例解释2

在区间 ([10, 20]) 内，( 30 = 2 \times 3 \times 5 ) 有 3 个不同的质因数，满足条件。

解题思路

此问题不仅需要质因数分解，还需要确定分解后的质因数数量。由于直接对每个数进行质因数分解效率不高，特别是在大区间处理时，我们可以预先使用筛法，比如埃拉托斯特尼筛法或欧拉筛法，来找出所有质数，并快速计算区间内每个数的质因数数量。

以下是C++解答的基本框架：

#include <iostream>
#include <vector>using namespace std;const int MAXN = 1000000;
vector<int> smallestPrimeFactor(MAXN + 1, 0);// 埃拉托斯特尼筛法初始化最小质因数
void sieve() {for (int i = 2; i <= MAXN; ++i) {if (smallestPrimeFactor[i] == 0) { // i is a primefor (int j = i; j <= MAXN; j += i) {if (smallestPrimeFactor[j] == 0) {smallestPrimeFactor[j] = i;}}}}
}// 计算有 K 个不同质因数的数字
int findSecretNumber(int L, int R, int K) {sieve();  // 初始化最小质因数表for (int num = L; num <= R; ++num) {int n = num;int factorCount = 0;while (n > 1) {int p = smallestPrimeFactor[n];factorCount++;while (n % p == 0) n /= p;}if (factorCount == K) return num;  // 找到符合条件的数}return -1;  // 没有找到
}int main() {int L, R, K;cin >> L >> R >> K;cout << findSecretNumber(L, R, K) << endl;return 0;
}

这个程序使用埃拉托斯特尼筛法预处理最小质因数，然后通过检查每个数的不同质因数数量来找出满足条件的秘密数字。