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