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

Exploring Pascal's pyramid 题号:154 难度: 65 中英对照

A triangular pyramid is constructed using spherical balls so that each ball rests on exactly three balls of the next lower level.

Then, we calculate the number of paths leading from the apex to each position:

A path starts at the apex and progresses downwards to any of the three spheres directly below the current position.

Consequently, the number of paths to reach a certain position is the sum of the numbers immediately above it (depending on the position, there are up to three numbers above it).

The result is Pascal's pyramid and the numbers at each level n are the coefficients of the trinomial expansion (x + y + z)n.

How many coefficients in the expansion of (x + y + z)200000 are multiples of 1012?


Solution

对$(x+y+z)^n$展开式的任一项可表示为 $$C_n^a C_{n-a}^b \times x^ay^bz^{n-a-b}$$ 设$c=n-a-b$,则其系数可以化简为 $$\frac{n!}{a!b!c!}$$ 那么只需要将$k!$包含的$p$的因子数量记作$f_p(k)$ 那么$f_2(n)-[f_2(a)+f_2(b)+f_2(c)]$和$f_5(n)-[f_5(a)+f_5(b)+f_5(c)]$就表示了该项系数包含$2,5$的因子数量。 只需要两类因子数量都超过12即可得该项系数能被$10^{12}$整除。

Code

public final class p154 {
    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 final int max = 200000;
	static int[] f5 = new int[max + 1];
	static int[] f2 = new int[max + 1];
	private static int repDiv(int n, int i) {
		int s = 0;
		while (n % i == 0) {
			s++;
			n /= i;
		}
		return s;
	}

    static public String run() {
		long ans = 0;

		for (int n = 1; n <= max; n++) {
			f5[n] = f5[n - 1] + repDiv(n, 5);
			f2[n] = f2[n - 1] + repDiv(n, 2);
		}

		int fives = f5[max] - 11;
		int twos = f2[max] - 11;

		for (int a = 0; 3 * a <= max; a++) {
			for (int b = a; a + 2 * b <= max; b++) {
				int c = max - a - b;

				int factors5 = f5[a] + f5[b] + f5[c];
				int factors2 = f2[a] + f2[b] + f2[c];

				if (factors5 < fives && factors2 < twos) {
					if (a == c)
						ans++;
					else if (a < b && b < c)
						ans += 6;
					else
						ans += 3;
				}
			}
		}
		return ""+ans;
	}
	
}
479742450
26908ms