poj3421

简单组合数学

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

#define maxn 10005

struct Factor
{
    int value, num;
} factor[maxn];

bool is[maxn];
int prm[maxn];
int num;
int n, m;
int sum;

int getprm(int n)
{
    int i, j, k = 0;
    int s, e = (int) (sqrt(0.0 + n) + 1);

    memset(is, 1, sizeof(is));
    prm[k++] = 2;
    is[0] = is[1] = 0;
    for (i = 4; i < n; i += 2)
        is[i] = 0;
    for (i = 3; i < e; i += 2)
        if (is[i])
        {
            prm[k++] = i;
            for (s = i * 2, j = i * i; j < n; j += s)
                is[j] = 0;
        }
    for (; i < n; i += 2)
        if (is[i])
            prm[k++] = i;
    return k;
}

void dissect(int n)
{
    num = 0;
    sum = 0;
    for (int i = 0; prm[i] * prm[i] <= n && i <= m; i++)
        if (n % prm[i] == 0)
        {
            factor[num].value = i;
            factor[num].num = 0;
            while (n % prm[i] == 0)
            {
                n /= prm[i];
                factor[num].num++;
            }
            sum += factor[num].num;
            num++;
        }
    if (n > 1)
    {
        factor[num].value = n;
        factor[num++].num = 1;
        sum++;
    }
}

long long com(int n, int r)
{
    if (n - r < r)
        r = n - r;
    int i, j;
    long long s = 1;
    for (i = 0, j = 1; i < r; ++i)
    {
        s *= (n - i);
        for (; j <= r && s % j == 0; ++j)
            s /= j;
    }
//    printf("%d %d %lld\n", n, r, s);
    return s;
}

int main()
{
    //freopen("t.txt", "r", stdin);
    m = getprm(10000);
    while (~scanf("%d", &n))
    {
        dissect(n);
        long long ans = 1;
        int temp = sum;
        for (int i = 0; i < num; i++)
        {
            ans *= com(temp, factor[i].num);
            temp -= factor[i].num;
        }
        printf("%d %lld\n", sum, ans);
    }
    return 0;
}