洛谷,https://www.luogu.com.cn/problem/P2043。
我的OJ,http://47.110.135.197/problem.php?id=5279。
题目描述对 N! 进行质因子分解。
输入格式输入数据仅有一行包含一个正整数 N,N <= 10000。
输出格式输出数据包含若干行,每行两个正整数 p,a,中间用一个空格隔开。表示 N! 包含 a 个质因子 p,要求按 p 的值从小到大输出。
输入样例 10 输出样例 2 83 45 27 1 样例说明 数据规模N ≤ 10000。
题解报告 题意分析非常简单的一个质因数分解题目。属于数论的知识点。
本题唯一的难度在于不能直接求解 N!,因为我们知道 C++ 中固有数据类型中,能表示最大的数据为 2^64-1,也就是 unsigned long long 类型。有些记不清楚了,好像 23! 就超过了 2^64-1 这个数据。而题目中给出的 N 最大值为 1000。
本题为的考点就是数论中的质因数分解。我们可以参考质数判定来实现,再使用 STL 中的 map 这个数据类型对结果进行保存,就可以满足本题的要求。
质因数分解思路就是从 2 开始,利用质数逐一判断。代码如下。
map<int, int> ans;//对x求质因数void factor(int x) { for (int i=2; i*i<=x; i++) { while (0==x%i) { ans[i]++; x /= i; } } if (x>1) { ans[x]++; }}注意函数中的 for 循环里套了一个 while 循环,其目的是实现对某个质数幂进行判断。
如 1024 = 2^10,通过这个函数,我们可以分解出 2 和 10。
样例数据分析N = 10,10! = 10*9*8*7*6*5*4*3*2,但是我们不能直接计算 10!,因为 N 大了,数据会超过 C++ 表示的范围,同时也是没有必要进行阶乘计算。我们只需要使用循环分解分别求 10、9、8、7、6、5、4、3、2 的质因数即可。
10 = (2^1) * (5^1)
9 = (3^2)
8 = (2^3)
7 = (7^1)
6 = (2^1) * (3^1)
5 = (5^1)
4 = (2^2)
3 = (3^1)
2 = (2^2)
这样,我们就知道了 10! 最终可以表示为:(2^8) * (3^4) * (5^2) * (7^1)。
数据规模分析N ≤ 10000。同时通过上面的样例数据分析过程,我们可以推断,使用 int 表示足够。
算法思路1、读入 N。
2、质因数分解函数。
3、从 2 到 N 循环,对每个 i 进行质因数分解。
4、输出。
AC 参考代码 #include <bits/stdc++.h>using namespace std;map<int, int> ans;//对x求质因数void factor(int x) { for (int i=2; i*i<=x; i++) { while (0==x%i) { ans[i]++; x /= i; } } if (x>1) { ans[x]++; }}int main() { int n; cin>>n; for (int i=2; i<=n; i++) { factor(i); } map<int, int>::iterator it; for (it=ans.begin(); it!=ans.end(); it++) { cout << it->first << " " << it->second << endl; } return 0;}