SHOW:
|
|
- or go back to the newest paste.
1 | import java.math.BigInteger; | |
2 | import java.util.ArrayList; | |
3 | ||
4 | public class Binomial { | |
5 | //PRIME SIEVE FOR DECOMPOSITION | |
6 | static boolean[] bs; | |
7 | static ArrayList<Integer> all_primes; | |
8 | static long size; | |
9 | public static void sieve(long upperbound){ | |
10 | size = upperbound + 1; // we add 1 to include upperbound | |
11 | bs = new boolean[(int) size]; | |
12 | all_primes = new ArrayList<>(); | |
13 | ||
14 | for(long i = 2 ; i < size ; i++){ | |
15 | if(!bs[(int)i]){ | |
16 | for(long j = i*i ; j < size ; j+=i){ | |
17 | bs[(int)j] = true; | |
18 | } | |
19 | all_primes.add((int)i); | |
20 | } | |
21 | } | |
22 | } | |
23 | //PRIME SIEVE CODE ENDS | |
24 | ||
25 | //Implementation with prime factor decomposition. VERY FAST for big values of N. | |
26 | //(Source: Computing Binomial Coefficients, P. Goetgheluck) | |
27 | - | //Requires a list of all primes less than N (generated once by the sieve) |
27 | + | //Requires a list of all primes less than or equal to N (generated once by the sieve) |
28 | - | //REMEMBER TO CALL SIEVE FUNCTION BEFORE CALLING COMBINATION, ALSO MAKE SURE ALL PRIMES LESS THAN N ARE GENERATED |
28 | + | //REMEMBER TO CALL SIEVE FUNCTION BEFORE CALLING COMBINATION, ALSO MAKE SURE ALL PRIMES LESS THAN OR EQUAL TO N ARE GENERATED |
29 | public static BigInteger combination(int N, int K){ | |
30 | if ((K == 0) || (K == N)) return BigInteger.ONE; | |
31 | K = Math.min(N-K, K); | |
32 | int nk = N - K; | |
33 | int rootN = (int) Math.sqrt(N); | |
34 | int n_half = N/2; | |
35 | ArrayList<Integer> exponents = new ArrayList<>(); //list of the exponents of the prime factorization. | |
36 | //example: exponents = {2, 0, 1} means that the answer is 2^2 * 3^0 * 5^1 | |
37 | ||
38 | for(int prime : all_primes){ | |
39 | if(prime > N) break; | |
40 | ||
41 | if (prime > nk) exponents.add(1); | |
42 | else if (prime > n_half) exponents.add(0); | |
43 | else if (prime > rootN){ | |
44 | if (N % prime < K % prime) exponents.add(1); | |
45 | else exponents.add(0); | |
46 | } | |
47 | else{ | |
48 | int r = 0, tmpN = N, tmpK = K, a, b, total = 0; | |
49 | ||
50 | while(tmpN > 0){ | |
51 | a = tmpN % prime; | |
52 | b = (tmpK%prime) + r; | |
53 | tmpN /= prime; | |
54 | tmpK /= prime; | |
55 | ||
56 | if(a<b){ | |
57 | total++; | |
58 | r = 1; | |
59 | } | |
60 | else r = 0; | |
61 | } | |
62 | exponents.add(total); | |
63 | } | |
64 | } | |
65 | ||
66 | //joining all prime factors in one BigInteger | |
67 | BigInteger R = BigInteger.ONE; | |
68 | for(int i = 0, len = exponents.size(); i<len; i++){ | |
69 | int exp = exponents.get(i); | |
70 | if(exp > 0) R = R.multiply(BigInteger.valueOf((long) Math.pow(all_primes.get(i), exp))); | |
71 | } | |
72 | ||
73 | return R; | |
74 | } | |
75 | ||
76 | public static void main(String[] args) { | |
77 | - | int N = 10000000; |
77 | + | int N = 3; |
78 | sieve(N); | |
79 | - | System.out.println(combination(N, N/2)); |
79 | + | System.out.println(combination(N, 2)); |
80 | } | |
81 | } |