当前位置:首页 » Project Euler » 详细页

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

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

1
11
121
1331
14641
15101051
1615201561
172135352171
.........

Solution

由题意知解题思路如下: - 构建杨辉三角,杨辉三角满足如下性质:第$n$行第 $k$个数字等于第 $n-1$行的第 $ k-1$个数字与第 $k$个数字的和,用$C^k_n$表示第$n$行第$k$个数字,即
![组合公式](https://ooo.0o0.ooo/2017/05/07/590ebbd19aac1.png)
其中$C^k_n$表示第$n$行第$k$个数字,将杨辉三角存储在Arraylist 中。 - 将得到的杨辉三角数组元素遍历去除重复元素。 - 参考第193题的解题思想,对去重数组元素遍历判断是否是square free number,若是,将该元素结果相加,遍历完得到满足条件所有square free number的和。 此题中理解杨辉三角递归构造和判断square free number 是关键。

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++) {
                list.add(line[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