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

Same differences 题号:135 难度: 45 中英对照

Given the positive integers, x, y, and z, are consecutive terms of an arithmetic progression, the least value of the positive integer, n, for which the equation, x2y2z2 = n, has exactly two solutions is n = 27:

342 − 272 − 202 = 122 − 92 − 62 = 27

It turns out that n = 1155 is the least value which has exactly ten solutions.

How many values of n less than one million have exactly ten distinct solutions?

Solution

设$x=m,y=m-k,z=m-2k$,$x,y,z$为递减的等差数列,则$x^2-y^2-z^2=(m-k)(5k-m)$。 一方面,要使得$x,y,z$全正,则$m>0,k>0,2k< m$。 另一方面,要求$x^2-y^2-z^2=(m-k)(5k-m)>0$,又有$m>k$,则$5k>m$。 所以 $$\frac{m}{5}< k < \frac{m}{2}$$ 搜索范围: 由于$x^2-y^2-z^2=(m-k)(5k-m)\geq m-k > \frac{m}{2}$,则$\frac{m}{2}< x^2-y^2-z^2< 10^6$。 所以$0< m < 2\times 10^6$

Code

public final class p135 {
    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(){
    	final int LIMIT=1000000;
		int[] solutions = new int[LIMIT];
		for (int m = 1; m < LIMIT * 2; m++) {
			for (int k = m / 5 + 1; k * 2 < m; k++) {
				long temp = (long)(m - k) * (k * 5 - m);
				if (temp >= solutions.length)
					break;
				solutions[(int)temp]++;
			}
		}
		
		int count = 0;
		for (int x : solutions) {
			if (x == 10)
				count++;
		}
		return Integer.toString(count);
    }

}
4989
33ms