Poj 3421: X-factor Chains

題目

分析

當

n = p[1]^a[1] * p[2]^a[2] * ... * p[m]^a[m]

則 n 的最長序列長度為

a[1] + a[2] + ... + a[m]

因為 最長序列即為從 1 開始，將質因數（含重覆）一個一個乘上去。

那這個長度的序列有幾個呢？答案是

(a[1]+a[2] + ... + a[m])! / ( (a[1]!)(a[2]!)...(a[m]!) )

即 質因數乘上去的順序做不盡相異物排列

以 120 為例，120 = 2 * 2 * 2 * 3 * 5。

從 1 開始，將質因數一個一個乘上去，因乘上去的順序不同，產生的序列也不同。

其中一個最長序列為：

1	,	2	,	4	,	8	,	24	,	120
	*2		*2		*2		*3		*5

另一個最長序列：

1	,	3	,	6	,	30	,	60	,	120
	*3		*2		*5		*2		*2

根據題目定義，此序列的長度為 5，也就是 3 + 1 + 1

*2, *2, *2, *3, *5 做不盡相異物排列得 5! / (3! * 1! * 1!) = 20

實作時，先建質數表（<= sqrt(2^20) = 1024），之後針對每個 input 質因數分解並計算其答案

※ 不盡相異物排列時需要用到 unsigned long long

AC Code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

typedef pair<int, int> pii;
typedef unsigned long long ull;

const int N = 1024;
bool is_prime[N];
vector<int> primes;

void init() {
    fill(is_prime, is_prime + N, true);

    primes.push_back(2);
    primes.push_back(3);
    primes.push_back(5);

    for (int i = 4; i < N; i += 2)
        is_prime[i] = false;
    for (int i = 9; i < N; i += 3)
        is_prime[i] = false;
    for (int i = 25; i < N; i+= 5)
        is_prime[i] = false;

    for (int i = 7; i < N; i += 2) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * i; j < N; j += i)
                is_prime[j] = false;
        }
    }
}

vector<pii> factorize(int n) {
    vector<pii> pf;

    int sqn = int(sqrt(n));
    for (size_t i = 0; i < primes.size() && primes[i] <= sqn; i++) {
        int p = primes[i];
        int power = 0;

        while (n % p == 0) {
            power++;
            n /= p;
        }

        pf.push_back(pii(p, power));
    }

    if (n != 1)
        pf.push_back(pii(n, 1));

    return pf;
}

int main() {
    // build primes under 1024
    init();

    int n;
    while (scanf("%d", &n) != EOF) {
        vector<pii> pf = factorize(n);

        int length = 0;
        for (size_t i = 0; i < pf.size(); i++)
            length += pf[i].second;

        ull ans = 1;
        for (int i = 1; i <= length; i++)
            ans = ans * i;
        for (size_t i = 0; i < pf.size(); i++) {
            int power = pf[i].second;
            for (int j = 1; j <= power; j++)
                ans = ans / j;
        }

        printf("%d %llu\n", length, ans);
    }

    return 0;
}

amoshyc/poj3421.md

Poj 3421: X-factor Chains

題目

分析

AC Code