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;
输入数据较多,需要提高读取效率,考虑之前提到的提高效率的方法。