阶乘分解
题目 阶乘分解
思路分析
暴力 先算阶乘 再算质因数分解
阶乘用dfs或者dp写
#include<bits/stdc++.h>
using namespace std;
int dfs(int n){
if(n==1)
return 1;
return n*dfs(n-1);
}
const int N=1e6+10;
int f[N];
int main()
{
int n;
cin>>n;
// int x=dfs(n);
f[n]=n;
for(int i=n-1;i>=1;i--)
f[i]=i*f[i+1];
// cout<<f[1];
int x=f[1];
for(int i=2;i<x/i;i++){
int s=0;
if(x%i==0){
while(x%i==0){
s++;
x/=i;
}
cout<<i<<" "<<s<<endl;
}
}
if(x>1)
cout<<x<<" "<<1<<endl;
return 0;
}
至于为什么是wa 而不是tle
其实是数据类型爆了 第二组数据直接要算100的阶乘 试问用什么数据类型来存呢
显然先算阶乘再做分解是不可行的
有什么办法不做阶乘 还能进行分解？
这其实就是引入了一个新的质因数分解的方式
一般做组合数的题目都要进行质因数的分解，我们一般是for循环对每个数进行质因数分解，大多数情况都不会超时，但极少数的情况下，题目会不允许这样的做法，所以我们需要学会一种更快的方法来求质因数。
我们一般的方法是对每个数进行质因数分解：
for(int i=2;i<=n/i;i++){
while(n%i==0){
h[i]++,n/=i;
}
}
if(n>1)
h[n]++;//大于sqrt(n) 的质因子 要么没有 要么只有一个
如果要做到更快的分解 可以直接对n!进行分解
比如求8!中2的倍数 原本是算出8! 然后while去模上2 就可以得到2的数量 2作为底数 数量作为指数
不妨把表打出来
1 2 3 4 5 6 7 8 我们求得在8！中2的个数
1 1 1 1 首先我们先计算出2的倍数的个数：8/2=4
1 1 其次计算出4的倍数的个数：
8/4=2（上面求出了第一层，现在求第二层）
1
最后我们解出第三层的2的个数： 8/8=1
我们把4+2+1=7，所以一共7个2出现了。
即：cnt(x)=[n/(x^1)]+[n/(x^2)]+[n/(x^3)]+…(直到x的次方大于n)
到这里我们可以发现：我们平时求的方法是一列一列求的（就是每一个数算一遍），而这个方法我们每一行每一行的求，虽然效果一样，但求起来速度很快。值得学习。
故做法：
1.先把素数表打好
2.for循环把小于n的每个质数进行一次运算，用数组记录
3.结束
非常快
void factorize_factorial(int n, const set<int>& primes) {
for (int p : primes) {
if (p > n)
break;
int count = 0;
for (long long k = p; k <= n; k *= p) {
count += n / k;
}
cout << p << " " << count << endl;
}
}
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
bool isnot_prime[2*N];
set<int> get_primes(int n){
set<int> primes;
for(int i=2;i<=n;i++){
if(!isnot_prime[i]){
primes.insert(i);
for(int j=i;j<=n;j+=i)
isnot_prime[j]=true;
}
}
return primes;
}
// 计算N!的质因数分解
void factorize_factorial(int n, const set<int>& primes) {
for (int p : primes) {
if (p > n)
break;
int count = 0;
for (long long k = p; k <= n; k *= p) {
count += n / k;
}
cout << p << " " << count << endl;
}
}
int main() {
int N;
cin >> N;
auto primes = get_primes(N);
factorize_factorial(N, primes);
return 0;
}
💬 评论