AcWing 197. 阶乘分解
原题链接
中等
作者:
kRYST4L
,
2023-05-27 16:57:12
,
所有人可见
,
阅读 150
算法1:对1-n中的每一个数进行质因数分解,统计每个质因数之和,时间复杂度为$O(n\sqrt n)$,肯定会TLE
算法2:
- 先用欧拉筛,筛出1000000内的所有质数
- 对每个质数p,怎么统计1-n中p的总共次数是多少呢?
- $p$的总共次数=$p$的倍数个数+$p^2$的倍数个数+…+$p^k$的倍数个数,其中$p^k$是小于$n$中最大的$p$次幂
证明如下:
- 举个例子来说:比如n=8,p=2
- 其中2的总共次数为8次,因为1-8中有2、4、6、8里含有2,即1+2+2+3=8
- 套入公式中:2的总共次数=2的倍个数数+$2^2$的倍数个数+$2^3$的倍数个数=$n/2+n/2^2+n/2^3$=8
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1000010;
int primes[N],cnt;
bool st[N];
int n;
void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++)
{
st[i*primes[j]]=true;
if(i%primes[j]==0) break;
}
}
}
int main ()
{
cin>>n;
get_primes(N-1);//初始化筛出所有质数
for(int i=0;i<cnt;i++)
{
int p=primes[i];
int s=0;
for(int j=n;j;j/=p) s+=j/p;
if(s) cout<<p<<" "<<s<<endl;
}
}