CH 3101 - 阶乘分解

题目链接：传送门

题解：

$(1e6)!$ 这种数字，表示都表示不出来，想直接 $O(\sqrt{N})$ 分解质因数这种事情就不要想了。

考虑 $N!$ 的特殊性，这个数字的所有可能包含的质因子，就是 $1 \sim N$ 这些数所包含的质因子。因此，只需要考虑 $1 \sim N$ 这每个数字的质因子即可。

那么，不妨筛出属于 $1 \sim N$ 范围内的所有质数，对于每一个质数 $p$，$1 \sim N$ 中显然有 $\lfloor N/p \rfloor$ 个能够被 $p$ 整除的数字，也就是说 $N!$ 的质因子中，可以确定至少有这么 $\lfloor N/p \rfloor$ 个 $p$。换句话说，产生了 $\lfloor N/p \rfloor$ 的贡献。

然后，我们进一步考虑，$\lfloor N/p \rfloor$ 个能够被 $p$ 整除的数字中，显然还有 $\lfloor N/{p^2} \rfloor$ 个能够被 $p^2$ 整除的数字，这些数字产生进一步产生贡献 $\lfloor N/{p^2} \rfloor$，往后依次类推 $\lfloor N/{p^3} \rfloor, \lfloor N/{p^4} \rfloor, \cdots$。

AC代码：

#include<bits/stdc++.h>

#define pb(x) push_back(x)

using namespace std;

typedef long long ll;

int n;

const int MAX=1e6;

bool noprm[MAX+];

vector<int> prm;

void Erato(int n)

{

    noprm[]=noprm[]=;

    for(int i=;i<=n;i++)

    {

        if(noprm[i]) continue;

        prm.pb(i);

        for(int j=i;j<=n/i;j++) noprm[i*j]=;

    }

}

int main()

{

    ios::sync_with_stdio();

    cin.tie(), cout.tie();

    cin>>n;

    Erato(n);

    for(auto p:prm)

    {

        ll cnt=;

        for(ll x=p;x<=n;x*=p) cnt+=n/x;

        if(cnt>) cout<<p<<' '<<cnt<<'\n';

    }

}

巴特西

CH 3101 - 阶乘分解 - [埃筛]

最新文章

热门文章