题目描述
输入正整数 X,求 X 的大于 1 的因子组成的满足任意前一项都能整除后一项的严格递增序列的最大长度,以及满足最大长度的序列的个数。
输入格式
输入包含多组数据,每组数据占一行,包含一个正整数表示 X。
输出格式
对于每组数据,输出序列的最大长度以及满足最大长度的序列的个数。
每个结果占一行。
数据范围
1≤X≤220
样例
输入
2
3
4
10
100
输出
1 1
1 1
2 1
2 2
4 6
解释
-
筛素数 线性筛法
-
筛掉的一定是合数,且用其最小质数,p[j]一定小于等于i的最小质因子,p是从小到大枚举的,所以一定不会大于i($\frac{N}{p}$)的最小质因子,一旦等于最小就会被
if(i%primes[j]==0)break;
掉 -
合数一定会被筛掉
比如一个合数为N一定可以表示成,$N=p\frac{N}{p}$ 我们知道p是N的最小质因子,那么一定有$p\le\frac{N}{p}$的最小质因子,当$i= \frac{N}{p} \le N$ ,因为$p$是从小到大枚举去乘$i$,而$p$一定在前面枚举过了,所以一定会执行$ i<N$把他筛掉,就是说$p$一定存在。
C++ 代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = (1<<20)+10;
int primes[N],cnt;
int minp[N];
bool st[N];
void get_primes(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i])
{
minp[i]=i;
//i的最小质数是它本身
primes[cnt++]=i;
}
for(int j = 0;primes[j]*i<=n;j++)
{
int t = primes[j]*i;
st[t]=true;
minp[t]=primes[j];
if(i%primes[j]==0) break;
}
}
}
int main()
{
get_primes(N-1);
//预处理
int fact[30],sum[N];
int x;
while(scanf("%d",&x)!=-1)
{
int k=0,tot=0;
//k为次数
while(x>1)
{
int p = minp[x];
fact[k]=p,sum[k]=0;
while(x%p==0)
{
x/=p;
sum[k]++;
tot++;
}
k++;
}
LL res =1;
for(int i=1;i<=tot;i++)res*=i;
for(int i=0;i<k;i++)
for(int j=1;j<=sum[i];j++)
res /=j;
//总的阶乘除以次数的阶乘
printf("%d %lld\n",tot,res);
}
return 0;
}