题目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

from numba import jit
import time
@jit
def solve():
        c = 0
        for a in range(3, 250002):
                for b in range(1, (a-1)//2+1):
                        if 4*b*(a-b) <= 1000000:
                                c += 1
                        else:
                                break
        return c
tt = time.time()
print(solve())
print(time.time()-tt)

1572729
0.1520087718963623

永恒的蓝色梦想

C++ 3ms

#include<iostream>
#include<cmath>
 


int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    constexpr unsigned int UPPER_BOUND = 1000000, MAX_N =  UPPER_BOUND / 4 + 1;
    unsigned int n = 3, result = 0, temp = sqrt(UPPER_BOUND);


    do {
        result += (n - 3) >> 1;
        result++;
        n++;
    } while (n <= temp);
    
    
    do {
        temp = ceil(sqrt((unsigned long long)n * n - UPPER_BOUND));
        result += (n - temp - 2) >> 1;
        result++;
        n++;
    } while (n <= MAX_N);


    cout << result << endl;
    return 0;
}