榻榻米

榻榻米是一种长方形的垫子，常用于平铺房间的地板。

假定现在只有一种榻榻米，形状为$1\times 2$，考虑边长为a,b且面积$s=ab$为偶数的长方形房间，并假定$a\le b$。

铺设榻榻米时必须遵循不存在共用一个顶点的四个榻榻米的规则。例如，以下两种铺法中左边的铺法可行，而右边不可行，原因是红X处有四个榻榻米共用顶点。

由于这一规则的限制，有些面积为偶数的房间无法铺满榻榻米，记$T(s)$为面积为s且无法铺满榻榻米的房间种数。

最小的无法铺满榻榻米的房间面积为$s=7\times 10=70$，其它形状的面积为70的房间都能铺满榻榻米，这些房间的形状分别是：$1\times 70$、 $2\times 35$、$5\times 14$，因此$T(70)=1$。

可以验证，$T(1320)=5$，对应的五种房间分别是$20\times 66$、$22\times 60$、$24\times 55$、$30\times 44$、$33\times 40$。事实上$s=1320$也是能使$T(s)=5$的最小s。

求出能使$T(s)=200$的最小s。

本题难度:

解答

该文的第3.2和3.4节给出了平铺数量的计算公式。

根据其中的推论3.4和定理3.5可知，当且仅当存在满足以下条件的自然数k时边长为a,b的房间无法铺满榻榻米。

$$(a+1)k+2\le b\le(a-1)(k+1)-2.$$ 枚举a,k并统计b的数量，最终结果是85765680。

注：计算量较大，代码中打印了进度信息。

import math

target=100000000
d=[0]*(target+1)

for a in range(1,int(math.sqrt(target))+1):
    for k in range(1,target/(a*a+a)+1):
        for b in range((a+1)*k+2,(a-1)*(k+1)-1):
            if a*b<=100000000 and (a*b)%2==0:
                d[a*b]+=1
    if a%100==0:print a/100,"percent completed"
            

n=1
while d[n]!=200:
    n+=1
print n