### Squarefree Binomial Coefficients题号：203 难度： 25 中英对照

The binomial coefficients nCk can be arranged in triangular form, Pascal's triangle, like this:

 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1
.........

### Solution

![组合公式](https://ooo.0o0.ooo/2017/05/07/590ebbd19aac1.png)

### Code

import java.math.BigInteger;
import java.util.*;

public class p203 {
private static int N = 51;

public static void main(String args[]) {

long start = System.nanoTime();
long result = run();
long end = System.nanoTime();
System.out.println(result);
System.out.println((end - start) / 1000000 + "ms");
}

private static long run() {
ArrayList<Long> list = new ArrayList<>(0);
long line[] = {1};
// for循环生成杨辉三角,保存在list中
for (int i = 0; i < N; i++) {
for (int j = 0; j < line.length; j++) {
}
line = nextLine(line);
}

// list  中元素排序
Collections.sort(list);
// 移除list 中重复元素
removeDups(list);

BigInteger count = new BigInteger("0");

for (int i = 0; i < list.size(); i++) {
if (isSquareFree(list.get(i))) {
count = count.add(new BigInteger("" + list.get(i)));

}
}
return count.longValue();
}

private static void removeDups(ArrayList<Long> arr) {

for (int i = 0; i < arr.size(); i++) {
long curr = arr.get(i);
int j = i + 1;
while (j < arr.size() && curr == arr.get(j)) {
arr.remove(j);

}
}
}

private static long[] nextLine(long[] n) {
long[] next = new long[n.length + 1];
for (int i = 0; i < next.length; i++) {
if (i == 0 || i == next.length - 1) {
next[i] = 1;
} else
next[i] = n[i - 1] + n[i];
}
return next;
}

// 遍历判断是否是 square free number
public static boolean isSquareFree(long n) {
for (long i = 2; i <= n; i++) {
int count = 0;
while (n % i == 0) {
n /= i;
count++;
if (count == 2) return false;
}
}
return true;
}

}

34029210557338
3ms