CCF-CSP第32次认证第二题——因子化简【分解素因数方法】

发布于:2025-02-22 ⋅ 阅读:(188) ⋅ 点赞:(0)

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;

输入数据较多,需要提高读取效率,考虑之前提到的提高效率的方法。


网站公告

今日签到

点亮在社区的每一天
去签到