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

Exploring Pascal's triangle 题号:148 难度: 50 中英对照

We can easily verify that none of the entries in the first seven rows of Pascal's triangle are divisible by 7:

             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

However, if we check the first one hundred rows, we will find that only 2361 of the 5050 entries are not divisible by 7.

Find the number of entries which are not divisible by 7 in the first one billion (109) rows of Pascal's triangle.

Solution

首先找规律,注意到一个7行的包含$7\times (7+1) \div 2$个数字的三角,要么都被$7$整除,要么都不能被$7$整除。 所以把这样的一个三角块作为一个整体,记第1行的数字为这个三角的“尖顶”。 当尖顶模$7$余$k$时,若$k=0$,则整个三角包含28个数字都是7的倍数;否则整个三角的28个数字都和7互素。 值得注意的是,当尖顶在整个杨辉三角的左右边缘时,尖顶模$7$总余$1$。 当尖顶在杨辉三角中间时,例如第8行第8位数字是按照三角块排列的第2行第2个三角块的尖顶,它模$7$余$2$。 那么规律为:当尖顶$a$在杨辉三角中间时,考虑它左上和右上的三角块的尖顶$b$和$c$,那么$a=b+c\quad (mod 7)$。 把杨辉三角按三角块排列,每个三角块只写明其尖顶模$7$的值,代表整个三角块,此时构成一个新的杨辉三角: 1 1 1 1 2 1 1 3 3 1 …………… 1 6 1 6 1 6 1 1 0 0 0 0 0 0 1 注意到第8行的三角块尖顶只有首尾两个模$7$余$1$,中间全部归零了。(实际上是杨辉三角的第50行) 所以应当将总行数$n$按照$7$进制,从高位向低位逐渐模拟计数即可。 注:找规律已经能满足本题的需要,具体证明和推导过程请参考卢卡斯定理,可证得质数$p$整除$C_n^m$的充要条件是$n$和$m$的$p$进制减法必定发生借位。

Code

public final class p148 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }

    static public String run() {
		long n = 1000000000;
		long c = 1;
		long sum = 0;
		while (n > 0) {
			long k = 1;
			long i = 0;
			// checks divisibility by 7
			while (k * 7 < n) {
				k *= 7;
				i += 1;
			}
			long m = n / k;
			sum += c * m * (m + 1) / 2 * Math.pow(28, i);
			n -= k * m;
			c *= m + 1;
		}
		return sum+"";
	}
}
2129970655314432
0ms