题目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 万块瓷砖的话，可以形成多少种不同的薄板呢？
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 本帖最后由 永恒的蓝色梦想 于 2021-2-13 20:51 编辑
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;
}
页:
[1]