[Acwing] 197. 阶乘分解 筛法预处理

前言

传送门 :

思路

根据算数基本定理 N = p 1 a 1 ∗ p 2 a 2 . . . p n a n N = p1^{a1}*p2^{a2}...pn^{an} N=p1a1∗p2a2...pnan

又 N ! = N ∗ ( N − 1 ) ∗ ( N − 2 ) . . . 1 N! =N*(N-1)*(N-2)...1 N!=N∗(N−1)∗(N−2)...1

所以暴力解法我们可以知道

s u m ( N ! ) = p 1 a 1 + a 2 + . . . + a 3 + a k + p 2 a 1 + a 2 + . . + a k . . . sum(N!) = p1^{a_1+a_2+...+a_3+a_k}+p2^{a_1+a_2+..+a_k}... sum(N!)=p1a1​+a2​+...+a3​+ak​+p2a1​+a2​+..+ak​...

所有的 p p p都在 N N N内,所以我们可以先处理出所有的 p p p

然后遍历 p p p,求出所有 p p p的指数即可

Mycode

b

ool st[N];
int primes[N],cnt;

void get_Prime(int x){
	for(int i=2;i