X-factor Chains
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 7375 | Accepted: 2340 |
Description
Given a positive integer X, an X-factor chain of length m is a sequence of integers,
1 = X0, X1, X2, …, Xm = X
satisfying
Xi < Xi+1 and Xi | Xi+1 where a | b means a perfectly divides into b.
Now we are interested in the maximum length of X-factor chains and the number of chains of such length.
Input
The input consists of several test cases. Each contains a positive integer X (X ≤ 220).
Output
For each test case, output the maximum length and the number of such X-factors chains.
Sample Input
2
3
4
10
100
Sample Output
1 1
1 1
2 1
2 2
4 6
Source
POJ Monthly–2007.10.06, ailyanlu@zsu题意:1 = X0, X1, X2, …, Xm = X,X0~Xm都是X的因子并且递增,给出X求出最长的链,有几条最长的链。代码:
//最长链就是X的素因子的个数,数量就是这些素因子的排列组合(重复的只算一个)
//(全部质因子个数的阶乘)/(每个质因子个数的阶乘)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int MAXN = ;
int prime[MAXN+];
void getPrime()
{
memset(prime,,sizeof(prime));
for(int i = ;i <= MAXN;i++)
{
if(!prime[i])prime[++prime[]] = i;
for(int j = ;j <= prime[] && prime[j] <= MAXN/i;j++)
{
prime[prime[j]*i] = ;
if(i % prime[j] == )break;
}
}
}
int factor[][];//factor[i][0]存素因子,factor[i][1]存素因子的个数
int fatCnt;//不重复的素因子个数
int getFactors(long long x)
{
fatCnt = ;
long long tmp = x;
for(int i = ; prime[i] <= tmp/prime[i];i++)
{
factor[fatCnt][] = ;
if(tmp % prime[i] == )
{
factor[fatCnt][] = prime[i];
while(tmp % prime[i] == )
{
factor[fatCnt][] ++;
tmp /= prime[i];
}
fatCnt++;
}
}
if(tmp != )
{
factor[fatCnt][] = tmp;
factor[fatCnt++][] = ;
}
return fatCnt;
}
ll jc(int x){
ll s=;
for(int i=;i<=x;i++)
s*=i;
return s;
}
int main()
{
getPrime();
int x;
while(scanf("%d",&x)==){
getFactors(x);
int ans1=;
ll tmp=;
for(int i=;i<fatCnt;i++){
//cout<<factor[i][0]<<" "<<factor[i][1]<<endl;
ans1+=factor[i][];
tmp*=jc(factor[i][]);
}
printf("%d %lld\n",ans1,jc(ans1)/tmp);
}
return ;
}