X-factor Chains(POJ-3421)题解

以你之姓@ 2022-12-28 07:29 104阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入格式
     *  输出格式
     *  输入
     *  输出
     *  算法分析
 *  解题标程
 *  错题总结

--------------------

# 题目描述 #

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.

## 输入格式 ##

> The input consists of several test cases. Each contains a positive integer X (X ≤ 220).

## 输出格式 ##

> For each test case, output the maximum length and the number of such X-factors chains.

## 输入 ##

2  
    3  
    4  
    10  
    100

## 输出 ##

1 1  
    1 1  
    2 1  
    2 2  
    4 6

## 算法分析 ##

本题题意为将给出的`正整数X`，分解出它的因数。  
并且后一个因子要是前一个因子的2倍以上，因为因子是素数，如果顺序遍历素数表，那么后一个因子肯定就是前一个因子的2倍。  
输出中：  
1、第一个答案为：X的因子的最多的个数  
2、第二个答案为：有多少条链，所有因子排列组合的个数，因为存在重复的排列组合因此需要排除

> 例如：100，100=2*2*5\*5 排列组合有6种

**n个不同的数的全排列就是n！，除去重复的因子排序，即n！除以每个重复因子数的阶乘。**

# 解题标程 #

#include <iostream>
    #include <cstdlib>
    #include <cstdio>
    using namespace std;
    #define Max ((1<<20)+2)
    
    typedef long long ll;
    
    ll prime[Max];  //将所有素数一次存放在prime里
    ll a[Max];  //筛选素数
    ll init[25];  //2^20的数字最多有25个因子所以只需要计算到init[25] 
    
    void sieve()
    {
        
        //埃氏筛法
        ll num=0;
        memset(a, 1, sizeof(a));
        a[0]=a[1]=0;
        for(ll i=2;i<Max;i++){
        
            if(a[i]){
        
                prime[num++]=i;
                for(ll j=2*i;j<Max;j+=i)
                    a[j]=0;
            }
        }
        //埃氏筛法
        
        //计算每个长度的全排列
        init[1]=1;
        for(ll i=2;i<25;i++)
            init[i]=init[i-1]*i;
        //计算每个长度的全排列
    }
    
    int main(int argc, const char * argv[]) {
        
        ll n;
        sieve();
    
        while(scanf("%lld",&n)!=EOF){
        
            ll ans=0,i=0,t=1;
            ll u;
            //因式分解
            while(n>1){
        
                if(n%prime[i]==0){
          //能够分解成prime[i]为因子
                    u=0;
                    while(n%prime[i]==0){
        
                        n/=prime[i];
                        u++;
                    }
                    t*=init[u]; //记录重复的因子排序个数
                    ans+=u;
                }
                if(a[n]==1){
          //如果剩下的数字n就是素数
                    ans++;
                    break;
                }
                i++;
            }
            //因式分解
    
            //除去重复的因子排序
            ll p=init[ans];
            p/=t;
            //除去重复的因子排序
    
            cout << ans << " " << p << endl;
        }
        
        return 0;
    }

--------------------

# 错题总结 #

> **n个不同的数的全排列就是n！，除去重复的因子排序，即n！除以每个重复因子数的阶乘。**