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
23410100
Sample Output
1 11 12 12 24 6
Source
, ailyanlu@zsu
题意：
1 = X 0, X 1, X 2, …, Xm = X，X0~Xm都是X的因子并且递增，给出X求出最长的链，有几条最长的链。
代码：
//最长链就是X的素因子的个数，数量就是这些素因子的排列组合(重复的只算一个) //(全部质因子个数的阶乘)/(每个质因子个数的阶乘)#include#include #include using namespace std;typedef long long ll;const int MAXN = 2000000;int prime[MAXN+1];void getPrime(){ memset(prime,0,sizeof(prime)); for(int i = 2;i <= MAXN;i++) { if(!prime[i])prime[++prime[0]] = i; for(int j = 1;j <= prime[0] && prime[j] <= MAXN/i;j++) { prime[prime[j]*i] = 1; if(i % prime[j] == 0)break; } }}int factor[100][2];//factor[i][0]存素因子，factor[i][1]存素因子的个数int fatCnt;//不重复的素因子个数int getFactors(long long x){ fatCnt = 0; long long tmp = x; for(int i = 1; prime[i] <= tmp/prime[i];i++) { factor[fatCnt][1] = 0; if(tmp % prime[i] == 0 ) { factor[fatCnt][0] = prime[i]; while(tmp % prime[i] == 0) { factor[fatCnt][1] ++; tmp /= prime[i]; } fatCnt++; } } if(tmp != 1) { factor[fatCnt][0] = tmp; factor[fatCnt++][1] = 1; } return fatCnt;}ll jc(int x){ ll s=1; for(int i=2;i<=x;i++) s*=i; return s;}int main(){ getPrime(); int x; while(scanf("%d",&x)==1){ getFactors(x); int ans1=0; ll tmp=1; for(int i=0;i