Project Euler 174

题目

Counting the number of “hollow” square laminae that can form one, two, three, … distinct arrangements

We shall define a square lamina to be a square outline with a square “hole” so that the shape possesses vertical and horizontal symmetry.

Given eight tiles it is possible to form a lamina in only one way: \(3\times 3\) square with a \(1\times1\) hole in the middle. However, using thirty-two tiles it is possible to form two distinct laminae.

If \(t\) represents the number of tiles used, we shall say that \(t = 8\) is type \(L(1)\) and \(t = 32\) is type \(L(2)\).

Let \(N(n)\) be the number of \(t \le 1000000\) such that \(t\) is type \(L(n)\); for example, \(N(15)\) = \(832\).

What is \(\sum N(n)\) for \(1 \le n \le 10\)?

解决方案

与173题一样，令\(N=1000000\)。假设内部的正方形边长为\(a\)，边框的宽度为\(d\)，那么大正方形的边长为\(2d+a\)，这个边框使用了\((2d+a)^2-a^2=4d(a+d)\)个正方形。

计算出的式子有常数因子\(4\)，因此只需要\(\dfrac{N}{4}\)的空间。因此，直接枚举式子\(a(a+d)\)的值并统计即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1000000,Q=10;
const int M=N/4;
int cnt[M+4];
int main(){
    for(int a=1;a+1<=M;a++)
        for(int d=1;d*(d+a)<=M;d++)
            ++cnt[d*(a+d)];
    int ans=0;
    for(int i=1;i<=M;i++)
        if(0<cnt[i]&&cnt[i]<=Q) ++ans;
    printf("%d\n",ans);
}