Acwing.197.阶乘分解(题解) [操作系统入门]

Z时代
2024-01-10
分类：综合

给定整数 N ，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 $p_{i}$ 和 $c_{i}$ 即可。

输入格式

一个整数N。

输出格式

N! 分解质因数后的结果，共若干行，每行一对 $p_{i}, c_{i}$ ，表示含有 $p_{i}^{c_{i}}$ 项。按照 $p_{i}$ 从小到大的顺序输出。

数据范围

$1 \leq N \leq 10^{6}$

输入样例：

5

输出样例：

2 3 3 1 5 1

样例解释

$5! = 120 = 2^{3} * 3 * 5$

水题，分解质因数，然后看到一个不一样的做法，是真的惊艳到我了，或许以后能够借鉴他的思路，换个角度思考问题。

思路，先用筛子筛出(10^6)内的素数，然后考虑(n)这个数，对于每个素数(x)而言，(n)是(x)的(n/x)倍，也就是说，对于小于等于(x)的数，形如(x,2x,3x...kx)这种形式有(lfloor frac{n}{x} floor)个，那么很容易的得到，对于(x)而言，有(lfloor frac{n}{x} floor)个数是(x)的倍数，即能被(x)整除；然后我们将(x*x)与上面的含义一样，意为计算(n)有几个(x*x)的倍数，这一步操作我们将(n/x)，含义一样。

(Code:)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n,prime[N],tot;
bool st[N];
void init(){
    for(int i=2;i<=N;++i){
        if(!st[i]){
            prime[++tot] = i;
            if(i>=10000)continue;
            for(int j=i*i;j<=N;j+=i)st[j] = true;
        }
    }
}
int main(){
    init();
    scanf("%d",&n);
    for(int i=1;prime[i]<=n;++i){
        int now = n,ans = 0;
        while(now){
            ans+=(now/prime[i]);
            now/=prime[i];
        }
        printf("%d %d
",prime[i],ans);
    }
    return 0;
}