阶乘分解《算法竞赛进阶指南》 \Huge{阶乘分解《算法竞赛进阶指南》} 阶乘分解《算法竞赛进阶指南》
题目地址:197. 阶乘分解 - AcWing题库
题面
给定整数 N N N,试把阶乘 N ! N! N! 分解质因数,按照算术基本定理的形式输出分解结果中的 p i p_i pi 和 c i c_i ci 即可。
输入格式
一个整数 N N N。
输出格式
N ! N! N! 分解质因数后的结果,共若干行,每行一对 p i , c i p_i, c_i pi,ci,表示含有 p i c i p_i^{c_i} pici 项。按照 p i p_i pi 从小到大的顺序输出。
数据范围
3 ≤ N ≤ 1 0 6 3 \le N \le 10^6 3≤N≤106
输入样例:
5
输出样例:
2 3
3 1
5 1
样例解释
5 ! = 120 = 2 3 ∗ 3 ∗ 5 5! = 120 = 2^3 * 3 * 5 5!=120=23∗3∗5
思路
给定一个整数 n n n,然后要求将 n ! n! n!进行质因数分解,并且按照算术基本定理的形式输出分解结果中的 p i p_i pi 和 c i c_i ci 。
算数基本定理: N = p 1 c 1 × p 2 c 2 × . . . × p m c m N=p^{c_1}_1 \times p^{c_2}_2 \times...\times p^{c_m}_m N=p1c1×p2c2×...×pmcm
因此,我们求出小于 n n n中有多少个数是质数 x x x的倍数,即 n ! n! n!中有多少个 x x x相乘,也就是 x ? x^? x?,然后直接输出即可。
标程
vector<PII> p(N);
bool q[N];
int tot;
void primes(int n) {
for(int i = 2; i <= n; i ++ ) {
if(!q[i]) p[tot++].fi = i;
for(int j = 0; p[j].fi <= n / i; j ++ ) {
q[p[j].fi * i] = 1;
p[j].se ++;
if(i % p[j].fi == 0) break;
}
}
}
void Solved() {
int n; cin >> n;
primes(1e6);
for(int i = 2; i <= n; i ++ ) {
if(q[i]) continue;
LL x = i; int res = 0;
while(x <= n) res += n / x, x *= i;
cout << i << " " << res << endl;
}
}