Divisors poj2992

Divisors

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 9940		Accepted: 2924

Description

Your task in this problem is to determine the number of divisors of C_n^k. 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 C_n^k. For the input instances, this number does not exceed 2⁶³ - 1.

Sample Input

5 1
6 3
10 4

Sample Output

2
6
16

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<time.h>
 5 #include<iostream>
 6 #include<algorithm>
 7 using namespace std;
 8 int p[500]={0},t,pp[100];
 9 void init()
10 {
11     int i,j;
12     t=0;
13     for(i=2; i<500; i++)
14     {
15         if(!p[i])
16         {
17             p[t++]=i;
18             j=i*i;
19             while(j<500)
20             {
21                 p[j]=1;
22                 j+=i;
23             }
24         }
25     }
26 }
27 void fun(int n,int q)
28 {
29     int i,j,m,sum;
30     for(i=0; p[i]<=n&&i<t; i++)
31     {
32         m=n;
33         sum=0;
34         while(m)
35         {
36             m/=p[i];
37             sum+=m;
38         }
39         if(q)
40         pp[i]+=sum;
41         else pp[i]-=sum;
42     }
43 }
44 int main()
45 {
46     init();
47     int n,k,i;
48     while(~scanf("%d%d",&n,&k))
49     {
50         memset(pp,0,sizeof(pp));
51         fun(n,1);
52         fun(k,0);
53         fun(n-k,0);
54         long long sum=1;
55         for(i=0; i<t; i++)
56         {
57             if(pp[i])sum*=pp[i]+1;
58         }
59         printf("%lld
",sum);
60     }
61 }

View Code