Jishu - 组合数（组合因子数）

#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;
}