Divisors
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 9617 | Accepted: 2821 |
Description
Your task in this problem is to determine the number of divisors of Cnk. Just for fun -- or do you need any special reason for such a useful computation?
Input
The input consists of several instances. Each instance consists of a single line containing two integers n and k (0 ≤ k ≤ n ≤ 431), separated by a single space.
Output
For each instance, output a line containing exactly one integer -- the number of distinct divisors of Cnk. For the input instances, this number does not exceed 263 - 1.
Sample Input
5 1
6 3
10 4
Sample Output
2
6
16
Source
/*
题意: 求 组合数 C(n,m)= n! / ( (n - m)! * m! ) 的 因数 个数,n<=431 设 n 的标准质因数分解式为 n = p1^a1 * p2^a2 *...* pk^ak , p1,p2..pk是素数
则 n 的 因数 个数 = (a1+1) * (a2+1) *...* (ak+1)
对于任意素数 p ，n！中有（ n / p + n / p^2 + n / p^3 +...)个质因子 p
思路: 先打素数表,再对每个素数p求在C(n,m)的个数a,相乘即得结果 */ /*
1.
C(n,m)= n! / ( (n - m)! * m! ) 枚举求解对于每一个素数因子。
居然可以这样。
ans=fun(n,prime[i])-fun(n-m,prime[i])-fun(m,prime[i]);
仔细想想，感觉..哈哈。
2.还有一点，要提。因为本人书写的习惯很差，所以经常在遇到要用__int64 的时候
就全部都用了。这题数据很好，就卡在这了好几处。超时...
其实在素数打表的过程中，我们也有体会，用bool的速度远远要小于标记用int的速度。 */ #include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std; bool s[];
int prime[],len; void make_prime()
{
int i,j;
for(i=;i<=;i++)
s[i]=false;
len=; for(i=;i<=;i++)
if(s[i]==false)
{
prime[++len]=i;
for(j=i*;j<=;j=j+i)
s[j]=true;
}
} int fun(int n,int s)
{
int ans=;
while(n)
{
n=n/s;
ans=ans+n;
}
return ans;
} int main()
{
make_prime();
int n,m,i,ans;
__int64 sum;
while(scanf("%d%d",&n,&m)>)
{
sum=;
for(i=;i<=len;i++)
{
if(prime[i]>n)break;
ans=fun(n,prime[i])-fun(n-m,prime[i])-fun(m,prime[i]);
sum=sum*(ans+);
}
printf("%I64d\n",sum);
}
return ;
}