CCF-CSP第32次认证第二题——因子化简
官网链接：TUOJ
时间限制： 2.0 秒
空间限制： 512 MiB
题目背景
质数（又称“素数”）是指在大于 11 的自然数中，除了 11 和它本身以外不再有其他因数的自然数。
题目描述
小 P 同学在学习了素数的概念后得知，任意的正整数 𝑛n 都可以唯一地表示为若干素因子相乘的形式。如果正整数 𝑛n 有 𝑚m 个不同的素数因子 𝑝1,𝑝2,⋯,𝑝𝑚p1,p2,⋯,pm，则可以表示为：𝑛=𝑝1𝑡1×𝑝2𝑡2×⋯×𝑝𝑚𝑡𝑚n=p1t1×p2t2×⋯×pmtm。
小 P 认为，每个素因子对应的指数 𝑡𝑖ti 反映了该素因子对于 𝑛n 的重要程度。现设定一个阈值 𝑘k，如果某个素因子 𝑝𝑖pi 对应的指数 𝑡𝑖ti 小于 𝑘k，则认为该素因子不重要，可以将 𝑝𝑖𝑡𝑖piti 项从 𝑛n 中除去；反之则将 𝑝𝑖𝑡𝑖piti 项保留。最终剩余项的乘积就是 𝑛n 简化后的值，如果没有剩余项则认为简化后的值等于 11。
试编写程序处理 𝑞q 个查询：
- 每个查询包含两个正整数 𝑛n 和 𝑘k，要求计算按上述方法将 𝑛n 简化后的值。
输入格式
从标准输入读入数据。
输入共 𝑞+1q+1 行。
输入第一行包含一个正整数 𝑞q，表示查询的个数。
接下来 𝑞q 行每行包含两个正整数 𝑛n 和 𝑘k，表示一个查询。
输出格式
输出到标准输出。
输出共 𝑞q 行。
每行输出一个正整数，表示对应查询的结果。
样例输入
3
2155895064 3
2 2
10000000000 10
样例输出
2238728
1
10000000000
样例解释
查询一：
𝑛=23×32×234×107n=23×32×234×107
其中素因子 33 指数为 22，107107 指数为 11。将这两项从 𝑛n 中除去后，剩余项的乘积为 23×234=223872823×234=2238728。
查询二：
- 所有项均被除去，输出 11。
查询三：
- 所有项均保留，将 𝑛n 原样输出。
子任务
40%40% 的测试数据满足：𝑛≤1000n≤1000；
80%80% 的测试数据满足：𝑛≤105n≤105；
全部的测试数据满足：1<𝑛≤10101<n≤1010 且 1<𝑘,𝑞≤101<k,q≤10。
参考题解
#include <iostream>
#include <vector>
using namespace std;
struct Factor {
long long p;
int t;
};
vector<Factor> factorize(long long n) {
vector<Factor> factors;
//试除法分解因数
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) {
int cnt = 0;
while (n % i == 0) {
cnt ++;
n /= i;
}
factors.push_back({i, cnt});
}
}
if (n > 1) { //若最后n > 1，说明这个数本身就是一个质数
factors.push_back({n, 1});
}
return factors;
}
long long calculate_result(const vector<Factor>& factors, int k) {
long long result = 1;
for (const auto& f : factors) {
if (f.t >= k) {
long long power = 1;
for (int i = 0; i < f.t; i++) {
power *= f.p;
}
result *= power;
}
}
return result;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long q;
cin >> q;
while(q--) {
long long n;
int k;
cin >> n >> k;
vector<Factor>factors = factorize(n);
cout << calculate_result(factors, k) << '\n';
}
return 0;
}
优化
改为使用pow函数计算
long long calculate_result(const vector<Factor>& factors, int k) {
long long result = 1;
for (const auto& f : factors) {
if (f.t >= k) {
result *= pow(f.p, f.t); // 使用pow计算幂
}
}
return result;
}
总结
本题难点在于如何分解得到给定数的素因数，第二题，要求较低，使用试除法即可满足题目要求。
试除法：试除法是整数分解算法中最简单和最容易理解的算法，用小于等于n的每个素数去试除待分解的整数。-- 优化点：只需要除到sqrt(n)
刚开始我一直在想怎么求所有的素数，再一个一个除，试试能不能除尽，思路就偏了，也很难实现。
从2开始，一直到sqrt(n)，尝试每个数i是否能整除n。如果能的话，就一直除以i，记录次数。这里要注意，i必须是质数，但试除法的时候其实不管是不是质数，比如当i是4的时候，此时n已经被2除尽了，所以4不会整除n。所以试除法中，i从2开始递增，每次如果能整除的话，就会一直除到不能除为止，这样后面的i就不会是合数了。比如，当处理完i=2后，n中的因子2已经被完全除掉了，所以后续的i=4的时候n已经不会被4整除了。
注意点：
全部的测试数据满足：1<𝑛≤10^10，int不够用，故使用long long；
输入数据较多，需要提高读取效率，考虑之前提到的提高效率的方法。