poj3421

maksyuki 发表于 oj 分类，标签: 数论-素因子分解, 组合数学-计数

15 10月 2015

X-factor Chains

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

2
3
4
10
100

Sample Output

1 1

2 1

2 2

4 6

Source

POJ Monthly--2007.10.06, ailyanlu@zsu

题目类型：整数素因子分解+组合计数

算法分析：为了得到最长的序列，除了头尾1和n之外，其他的约数应该按照递增排列且后一个约数要比前一个恰好多一个素因子，这样才能保证得到的序列是最长的。最长序列的数目是素因子幂和的可重排列(即素因子幂之和的阶乘/每个素因子幂的阶乘)

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e7 + 48579;

LL fac[27];

void PP ()
{
    fac[1] = 1;
    for (LL i = 2; i <= 21; i++)
        fac[i] = fac[i-1] * i;
}

int aa[maxn], len;

int main()
{
//    CFF;
    PP ();
    int n;
    while (scanf ("%d", &n) != EOF)
    {
        int res = 0;
        len = 0;
        for (int i = 2; i * i <= n; i++)
        {
            while (n % i == 0)
            {
                n /= i;
                aa[len++] = i;
                res++;
            }
        }

        if (n > 1)
        {
            aa[len++] = n;
            res++;
        }

        LL ans = fac[res], tt = 0;
        for (int i = 1; i < len; )
        {
            if (aa[i-1] == aa[i])
            {
                while (i < len && aa[i-1] == aa[i])
                {
                    tt++;
                    i++;
                }
            }

            else
            {
                ans /= fac[tt+1];
                tt = 0;
                i++;
            }
        }

        if (tt)
            ans /= fac[tt+1];

        printf ("%d %lld\n", res, ans);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e7 + 48579;

LL fac[27];

void PP ()

{

fac[1] = 1;

for (LL i = 2; i <= 21; i++)

fac[i] = fac[i-1] * i;

}

int aa[maxn], len;

int main()

{

// CFF;

PP ();

int n;

while (scanf ("%d", &n) != EOF)

{

int res = 0;

len = 0;

for (int i = 2; i * i <= n; i++)

{

while (n % i == 0)

{

n /= i;

aa[len++] = i;

res++;

}

if (n > 1)

{

aa[len++] = n;

res++;

}

LL ans = fac[res], tt = 0;

for (int i = 1; i < len; )

{

if (aa[i-1] == aa[i])

{

while (i < len && aa[i-1] == aa[i])

{

tt++;

i++;

}

else

{

ans /= fac[tt+1];

tt = 0;

i++;

}

if (tt)

ans /= fac[tt+1];

printf ("%d %lld\n", res, ans);

}

return 0;

}

poj3292

poj2739

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

poj3421

分类目录

标签云

书签

近期评论