POJ3421_X-factor Chains_素因子分解&&排列组合

X-factor Chains

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7257		Accepted: 2295

Description

Given a positive integer X, an X-factor chain of length m is a sequence of integers,

1 = X₀, X₁, X₂, …, X_m = X

satisfying

X_i < X_i+1 and X_i | X_i+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 ≤ 2²⁰).

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

给出一个整数 X， 就会存在一个数列， 第一项是 1， 前一项都能整除后一项， 最后一项是 X。

求这个数列的最大长度（不算 1）以及长度最大的数列的种数

前一项能整除后一项， 说明前一项是后一项的因子， 前一项乘以一个数 temp 等于后一项。为了让这个数列尽可能长， 应该让这个 temp 小到不能分解因子。 也就是说， temp是个素数。 因此， 这个题目就转化成了 X 的素因子分解。

数列的不同其实就是乘以各因子的先后顺序不同， 因此最长数列的数量问题就转化成了排列组合问题。注意相同因子的前后顺序不影响数列。

首先对X进行素因子分解， 然后求因子全排列的种数， 注意去掉相同因子的干扰。

#include<cstdio>
#include<iostream>

using namespace std;

const int maxn = 1100000;
typedef long long ll;
int exponent[25];

ll factorial(ll x)
{
for(ll i= x-1; i> 0; i--)
x *= i;
return x;
}

ll getfactor(ll x, ll &sum)
{
ll now = x, cnt = 0;

for(ll i= 2; i<= x/i; i++)
{
if(now%i == 0)
{
exponent[cnt] = 0;

while(now%i == 0)
{
sum ++;
exponent[cnt] ++;
now /= i;
}

cnt ++;
}
}

if(now != 1) sum ++;

return cnt;
}

int main ()
{
ll x;

while(~scanf("%lld", &x))
{
ll sum = 0;
ll cnt = getfactor(x, sum); 

ll path = factorial(sum);
for(ll i= 0; i< cnt; i++)
{
path /= factorial(exponent[i]);
}

printf("%lld %lld\n", sum, path);
}

return 0;
}