只有脚踩上去才知其远近和曲折

HZOJ 310 阶乘分解

解题思路

惯例素数打表

以 10! 为例:

10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10

如何计算含有多少个素因子 2 呢?

我们可以看出:

  • 每隔 2 个数便包含一个素因子 2;
  • 每隔 4 个数便包含一个素因子 2;
  • 每隔 8 个数便包含一个素因子 2;

所以包含含素因子 2 的个数为: \frac {n} {2} + \frac {n} {4} + \frac {n} {8} + \frac {n} {2^{[log_{2}n]}}

其他素因子求法同理

code

#include<iostream>
using namespace std;
#define MAXN 1000005
int prime[MAXN];

void init() {
    for (int i = 2; i < MAXN; i++) {
        if (!prime[i]) prime[++prime[0]] = i;
        for (int j = 1; j <= prime[0] && i * prime[j] < MAXN; j++) {
            prime[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
    return ;
}

int main() {
    int n;
    init();
    cin >> n;
    for (int i = 1; i <= prime[0] && prime[i] <= n; i++) {
        int ans = 0, temp = n;
        while (temp) { // 进行分割
            ans += temp / prime[i];
            temp /= prime[i];
        }
        cout << prime[i] << " " << ans << endl;
    }
    return 0;
}
点赞