Posted on 2008-12-13 16:17
Hero 閱讀(163)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
代碼如詩(shī)－－ACM
1 // 1091 C++ Accepted 0.015 121 KB URAL
2
3 //組合數(shù)學(xué)容斥原理
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 typedef long long llong ;
10
11 const int prime[15] = { 2,3,5,7,11,13,17,19,23,29 } ;
12
13 int ink, ins ;
14 llong out ;
15
16 llong C( int n, int k )
17 {
18 if( k > n ) return 0 ;
19
20 //if( k > (n-k) ) k = (n-k) ;
21
22 if( 0 == k ) return 1 ;
23 if( n == k ) return 1 ;
24 else return n*C( n-1, k-1 )/k ;
25 }
26
27 int main()
28 {
29 while( scanf( "%d %d", &ink, &ins ) != EOF )
30 {
31 out = 0 ;
32 for( int i=0; i<10; i++ )
33 {
34 if( prime[i]*ink > ins ) break ;
35
36 out += C( ins/prime[i], ink ) ;
37
38 if( out > 8000000 ) break ;
39 }
40
41 out -= C( ins/6, ink ) ;
42 out -= C( ins/10, ink ) ;
43 out -= C( ins/14, ink ) ;
44 out -= C( ins/15, ink ) ;
45 out -= C( ins/22, ink ) ;
46 out -= C( ins/21, ink ) ;
47
48 if( out > 10000 ) out = 10000 ;
49
50 printf( "%I64d\n", out ) ;
51 }
52
53 return 0 ;
54 }