题目173：使用最多100万块瓷砖可以形成多少不同的中空的正方形？

欧拉计划

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

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?

题目：

我们定义一个正方形薄板为一个中间为正方形空洞的正方形外框。这个形状在水平和竖直方向上都是对称的。比如，用 32 块方形砖，我们可以得到如下两个不同的薄板。

如果有 100 块砖，而且不需要一次全部使用的话，我们可以形成 25 种不同的正方形薄板。

那么请问，如果使用不超过 100 万块瓷砖的话，可以形成多少种不同的薄板呢？

jerryxjr1220

1. from numba import jit
   
2. import time
   
3. @jit
   
4. def solve():
   
5.         c = 0
   
6.         for a in range(3, 250002):
   
7.                 for b in range(1, (a-1)//2+1):
   
8.                         if 4*b*(a-b) <= 1000000:
   
9.                                 c += 1
   
10.                         else:
    
11.                                 break
    
12.         return c
    
13. tt = time.time()
    
14. print(solve())
    
15. print(time.time()-tt)

复制代码

1572729
0.1520087718963623

永恒的蓝色梦想

C++ 3ms

1. #include<iostream>
   
2. #include<cmath>
   
3. 
   
4. 
   
5. 
   
6. int main() {
   
7.     using namespace std;
   
8.     ios::sync_with_stdio(false);
   
9. 
   
10.     constexpr unsigned int UPPER_BOUND = 1000000, MAX_N =  UPPER_BOUND / 4 + 1;
    
11.     unsigned int n = 3, result = 0, temp = sqrt(UPPER_BOUND);
    
12. 
    
13. 
    
14.     do {
    
15.         result += (n - 3) >> 1;
    
16.         result++;
    
17.         n++;
    
18.     } while (n <= temp);
    
19.    
    
20.    
    
21.     do {
    
22.         temp = ceil(sqrt((unsigned long long)n * n - UPPER_BOUND));
    
23.         result += (n - temp - 2) >> 1;
    
24.         result++;
    
25.         n++;
    
26.     } while (n <= MAX_N);
    
27. 
    
28. 
    
29.     cout << result << endl;
    
30.     return 0;
    
31. }

复制代码