题解 | #阶乘分解#

链接

对于这道题目，其实理解了线性筛法和一个例子就变得格外简单了，这道阶乘分解，非质数不能被输出，所以我们要将质数标记，那这个时候我们就需要用到线性筛质数了，是代码中的函数get_prime()，之后我们要做的就是输出非质数的，但这个数的指数是多少我们怎么得到呢?

我们可以举一个例子来理解一下如何得到阶乘里的某个质数的指数

例如我们要求8的阶乘分解，我们这时要输出2的指数为多少； 1 2 3 4 5 6 7 8

可以看到，有四个数字是2的倍数，也就是:2 4 6 8

之后我们再看4的倍数有多少:4 8

再看八的倍数:8

所以我们最后容易得到2的指数即为4+2+1=7

为什么这样一定能得到其指数呢，其实就相当于每次都让基数(这里是2)乘2，相当于对目标数字除以2，

再举一个例子

比如一开始是2 4 6 8，这时候我们得到了4个2因子

然后我们使得这四个数全都除2

变成了1 2 3 4

这时候还是2的倍数的就剩下两个了，又得到两个2的因子

我们再除以2

变成0 1 1 2

这时候就只有一个2的因子，我们过程中得到的因子全都加起来就得到了最终的答案

了，使得我们能够找到所有数字的2的因数个数

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#define int long long

using namespace std;

const int PS = 1e6 + 10;//要筛得的质数范围 

int fg[1000010];
int zs[1000010];

void get_prime()
{//欧拉线性筛法 
	 for(int i=2;i<=PS;i++)
	 {
	 	if(fg[i]==1) continue;
	 	zs[++zs[0]]=i;//是质数，存入,zs[0]的值就是范围内质数的个数 
	 	for(int o=2;o*i<=PS;o++) fg[i*o]=1;//标记不是质数的 
	 }
}//目前我见过的最好的一个质数筛板子，一下子就能看明白 

void solve()
{
	get_prime();
	int n;cin>>n;
	for(int i=2;i<=n;i++)
	{
		if(fg[i]==1) continue;
		int sum=0;
		for(int o=i;o<=n;o*=i)
		{
			sum=sum+(n/o);
		}
		if(sum==0) continue;
		else cout<<i<<" "<<sum<<endl;
	}
}

signed main()
{
	IOS;
	int T=1;
//	cin>>T;
	while(T--) solve();
	return 0;
}