题目 Contest Hunter 3101 阶乘分解

原题传送门

题目分析

• 这里介绍一个本蒟蒻自己\(yy\)出来的方法。

• 我们发现，对于某一个单个的整数\(n\)，若\(n\)能被某一个数\(x\)整除，那么我们可以看作\(++count[x]\)、且将\(n\)变为\(n/x\)。

• 这时就相当有了两个\(n/x\)继续分解，就相当于缩小了问题规模！！！

Code：

#include<cstdio>
#include<bitset>
//#include<bits/stdc++.h>
using namespace std;
#define rg register int
#define V inline void
#define I inline int
#define db double
#define B inline bool
#define ll long long
#define F1(i,a,b) for(rg i=a;i<=b;++i)
#define F3(i,a,b,c) for(rg i=a;i<=b;i+=c)
#define ed putchar('\n')
#define bl putchar(' ')
template<typename TP>V read(TP &x)
{
    TP f=1;x=0;register char c=getchar();
    for(;c>'9'||c<'0';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    x*=f;
}
template<typename TP>V print(TP x)
{
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int N=1000005;
bitset<N>v,vis;
int n,cnt,pri[N],c[N];
V make_prime_list()
{
    F1(i,2,n)
    {
        if(!v[i]) pri[++cnt]=i;
        for(rg j=1;j<=cnt && pri[j]*i<=n;++j)
        {
            v[pri[j]*i]=1;
            if(i%pri[j]==0) break;
        }
    }
}
int main()
{
    read(n),make_prime_list();//用质数去分解1~n的数 
    F1(i,1,n) c[i]=1;//初始化，刚开始相当于每个数都有 
    F1(i,1,cnt)
        for(rg j=2;j*pri[i]<=n;++j)//要从2开始，因为不能去除该质数本身 
        {
            if(vis[j*pri[i]]) continue;//不能重复分解数 
            rg sum=0,x=j*pri[i];
            while(x%pri[i]==0) ++sum,x/=pri[i];//要注意将这个数分解“干净” 
            c[x]+=c[j*pri[i]],c[pri[i]]+=sum*c[j*pri[i]];
            vis[j*pri[i]]=1,c[j*pri[i]]=0;//根据“题目分析” 
        }
    F1(i,1,cnt)
        if(c[pri[i]]) print(pri[i]),bl,print(c[pri[i]]),ed;
    return 0;
}