题目:
给定整数 N(1≤N≤10^6),试把阶乘 N! 分解质因数,按照算术基本定理的形式输出分解结果中的p_i 和 c_i 即可。
思路:
如果直接分别对2~N分解质因数,再将结果合成,那么时间复杂度过高会超时。显然N!的质因数不会超过N,那么先求出不超过N的所有素数p,再分别求出其在N!中的次数。对每一个素数p,其在N!中的次数等于在1~N中的次数之和。1~N中能被p整除的有⌊N/p⌋个数,能被p^2整除的有⌊N/p^2⌋个数(也就是说此时p的次数至少有⌊N/p⌋+⌊N/p^2⌋,其中⌊N/p^2⌋不必乘以2,因为被p^2整除的数也被p整除,而此前已经统计过一次p),以此类推,p的次数就有⌊N/p⌋+⌊N/p^2⌋+⌊N/p^3⌋+……+⌊N/p^⌊log(N)/log(p)⌋⌋. 每如此计算一次,时间复杂度为O(logN),则总复杂度为O(NlogN).
代码:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
#define MAX_N 1000005
int v[MAX_N];
int prime[MAX_N];
int c[MAX_N];
int m;
void primes(int n) {
m = 0;
memset(v, 0, sizeof(v));
memset(prime, 0, sizeof(prime));
for (int i = 2; i <= n; i++) {
if (v[i] == 0) {
v[i] = i;
prime[++m] = i;
}
for (int j = 1; j <= m; j++) {
if (prime[j] > v[i] || prime[j] > n / i) {
break;
}
v[i * prime[j]] = prime[j];
}
}
}
int main() {
int n;
cin >> n;
primes(n);
for (int i = 1; i <= m; i++) {
long long p = prime[i]; //最后一次极限情况相乘可能溢出所以用ll,有点坑,找了好久
int t = 0;
while (n/p) {
t += n / p;
p *= prime[i];
}
c[i] = t;
}
for (int i = 1; i <= m; i++) {
printf("%d %d\n", prime[i], c[i]);
}
return 0;
}