吉首 - 組合數(求組合數因子個數)

題目連結:http://120.78.162.102/problem.php?id=6240

時間限制: 1 Sec  記憶體限制: 128 MB

題目描述

求組合數C(N,M)，以及C(N,M)因子個數。

輸入

N和M，其中0<=M<=N<=50,以EOF結束。

輸出

該組合數結果。

樣例輸入

樣例輸出

解題思路

#include <math.h>
#include <stdio.h>
#include <string.h>
long long a[60][60];
const int maxn = 60;
int vis[maxn], dp[maxn][maxn];
void C()
{
    memset(a, 0, sizeof(a));
    a[0][0] = 1;
    for (int i = 1; i <= 55; i++)
        a[1][i] = i,a[0][i] = 1;
    for (int r = 2 ; r <= 55 ; r++)
        for (int c = r; c <= 55; c++)
            a[r][c] = a[r][c - 1] + a[r - 1][c - 1];
}
void sieve(int n)
{
    int m = sqrt(n + 0.5);
    memset(vis, 0, sizeof(vis));
    vis[0] = vis[1] = 1;
    for (int i = 2; i <= m; i++)
        if (!vis[i])
            for (int j = i * i; j <= n; j += i)
                vis[j] = 1;
}
int get(int n, int m)
{
    int sum = 0;
    while (n)
    {
        sum += n / m;
        n /= m;
    }
    return sum;
}
void pre(int n)
{
    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= i; j++)
            dp[i][j] = get(i, j);
}
int MM(int n, int m)
{
    pre(55);
    sieve(55);
    long long ans = 1;
    for (int i = 2; i <= n; i++)
        if (!vis[i])
            ans *= dp[n][i] - dp[m][i] - dp[n - m][i] + 1;
    return ans;
}
int main()
{
    C();
    int n, m;
    while (~scanf("%d%d", &n, &m))
        printf("%lld %lld\n", a[m][n], MM(n, m));
    return 0;
}