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

Using up to one million tiles how many different "hollow" square laminae can be formed? 题号:173 难度: 30 中英对照

We shall define a square lamina to be a square outline with a square "hole" so that the shape possesses vertical and horizontal symmetry. For example, using exactly thirty-two square tiles we can form two different square laminae:

With one-hundred tiles, and not necessarily using all of the tiles at one time, it is possible to form forty-one different square laminae.

Using up to one million tiles how many different square laminae can be formed?


Solution

设使用的正方形的总数目为Z,外圈正方形的边长为X,内圈正方形的边长为Y。 1. 当Z=一百万时,正方形的边长最多为Z/4=250000。当X=250001时,组成的正方形刚好用了一百万个正方形。 2. Y一定比X少2的倍数个正方形,否则就构不成正方形环。例如,X=3时,Y=1才能构成正方形环;X=5时,Y=1或者Y=5都能构成正方形环。 3. 最多只能用一百万个正方形,即$$0 < X^2 - Y^2 \leq Z$$ 所以,只需根据上述条件遍历X和Y,就能得出最多能构成的正方形环数。

Code


public final  class p173 {
		 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" );
		 }	
		 public static long run()
		 {
			int count = 0;
			// One million tiles means that each side can be a maximum of 250000 tiles long (four sides)
			// A side of 250001, however, uses exactly one million tiles if the ring is one tile in width
			for(int X = 3; X <= 250001; X++) {
				// Starts at n - 2 because the Y square must be one smaller from all sides
				// e.g: one square from the left and one square from the right = total length minus 2
				for(int Y = X - 2; Y >= 1; Y -= 2) {
					// Make sure that less than 1000000 tiles are used
					if(((long) X * X) - ((long) Y * Y) > 1000000) {
						break;
					}
					count++;
				}
			}
			return count;
		 }
}
1572729
5ms