程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ_3421_X-factor Chains(素數篩法)

POJ_3421_X-factor Chains(素數篩法)

編輯：C++入門知識

POJ_3421_X-factor Chains(素數篩法)

X-factor Chains Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 5659 Accepted: 1786

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₊₁ and X_i | X_i₊₁ 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

Sample Output

題意：給你一個數X，將X分解成1~X的因子數列，前一個數可以整數後一個數，求滿足條件的最大鏈長以及有多少條這樣長的鏈。

分析：很容易想到了素因數分解。不難推出，我們要求的最大鏈長就等於素因子的個數，最長鏈條數就是這些素因子的排列組合數。題目數據量較大，所以先打個素數表。

題目鏈接：http://poj.org/problem?id=3421

代碼清單：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

const int maxp = 10000 + 5;
const int maxn = 1100000 + 5;

int sum,X;
int prime[maxp];
bool vis[maxn];
int num[maxp],k; //存每個素因子的個數

void init(){  //素數篩法打表
    sum=0;
    memset(vis,true,sizeof(vis));
    for(int i=2;i<=maxn;i++){
        if(!vis[i]) continue;
        prime[sum++]=i;
        if(i>(int)sqrt(maxn)) continue;
        for(int j=i*i;j<=maxn;j+=i)
            vis[j]=false;
    }
}

ll get_max(){  //得到最大鏈長，即素因子的個數
    ll ans=0;
    for(int i=0;i