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

Singleton difference 题号:136 难度: 50 中英对照

The positive integers, x, y, and z, are consecutive terms of an arithmetic progression. Given that n is a positive integer, the equation, x2y2z2 = n, has exactly one solution when n = 20:

132 − 102 − 72 = 20

In fact there are twenty-five values of n below one hundred for which the equation has a unique solution.

How many values of n less than fifty million have exactly one solution?

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< 5\times 10^7$。 所以$0< m < 2\times 5\times 10^7$

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=50000000;
		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 == 1)
				count++;
		}
		return Integer.toString(count);
    }

}
2544559
2883ms