Problem 256: Tatami-Free Rooms

Project Euler Problem 256 Solution

EulerSolve provides an optimized solution for Project Euler Problem 256, Tatami-Free Rooms, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For an admissible area $s$, every room shape is a factor pair $(a,b)$ with $$ab=s,\qquad a\le b.$$ The implementation defines $T(s)$ as the number of those rectangles that fail the tatami test used by the solver. The task is to find the smallest $s$ such that $$T(s)=\text{target},$$ with $\text{target}=200$ in the full Project Euler problem. The final numeric answer is intentionally omitted here. Mathematical Approach 1. Turn the Geometry into a Divisor Problem Once the area $s$ is fixed, there is no continuous geometry left to search: every candidate room is determined by a divisor $a$ of $s$, and the other side is $b=s/a$. Therefore $$T(s)=\sum_{\substack{a\mid s\\a\le \sqrt{s}}}\mathbf{1}_{\neg \mathrm{tileable}(a,s/a)}.$$ The condition $a\le \sqrt{s}$ ensures that each unordered pair is counted exactly once. So the whole problem becomes: for each $s$, enumerate its divisor pairs and test each pair with the arithmetic predicate from the code. 2. Why the Outer Search Uses Only Even $s$ The solver increments $s$ by 2 and never tests odd areas. This matches the room model encoded by the implementation: the predicate immediately rejects odd area, so the search space is reduced to even $s$ from the beginning. That single observation halves the outer search....

Detailed mathematical approach

Problem Summary

A room is a rectangle of $a\times b$ unit squares with integers $a\le b$ and even size $s=ab$. It must be covered completely, without overlap, by mats of size $1\times2$, and one rule must be obeyed: no point of the floor may be a corner of four different mats. Rooms that cannot be covered in this way are tatami-free, and $T(s)$ is the number of tatami-free rooms of size $s$. The smallest tatami-free room is $7\times10$, while $1\times70$, $2\times35$ and $5\times14$ can be covered, so $T(70)=1$. The tatami-free rooms of size $1320$ are $20\times66$, $22\times60$, $24\times55$, $30\times44$ and $33\times40$, so $T(1320)=5$, and $1320$ is the smallest size with $T(s)=5$. We must find the smallest size $s$ with $T(s)=200$. ^[1]

The whole solution in one sentence: a room $a\times b$ with $a\le b$ can be covered exactly when $b$ is within $k+1$ of a multiple $ka$ with $k\ge1$, so $T(s)$ is found by testing every divisor $a\le\sqrt s$ of $s$ with this rule, and a search over the even sizes stops at the first $s$ with exactly $200$ failures.

Mathematical Approach

We draw every room with its long side horizontal, so that it has $a$ rows and $b$ columns. The rule forces the mats of a covering into blocks whose widths depend only on $a$. Which lengths $b$ can be assembled from these widths is then a question about integers, and $T(s)$ becomes a count over the divisors of $s$.

1. The rule at one point

Take a grid point $P$ inside the room. The four squares around $P$ must not belong to four different mats, so one mat covers two of them, and $P$ is the midpoint of a long side of that mat: mats may meet in the shape of a T, never in the shape of a +, which is also the traditional rule for laying tatami. ^[4] For example, of the five coverings of a $2\times4$ room by $1\times2$ mats exactly one breaks the rule: four horizontal mats in two rows of two, which meet at the centre. A vertical mat at each end with two stacked horizontal mats between them is allowed, because each inner grid point lies in the middle of a long side of a mat.

2. Small rooms

An exhaustive computer search over all coverings shows which small rooms are tatami-free. Every room with $a\le6$ can be covered, and for $a=7,\dots,10$ the tatami-free rooms are:

$a=7$: $b=10$;
$a=8$: $b=11,12$;
$a=9$: $b=12,14,22$;
$a=10$: $b=13,14,15,16$ and $b=24,25$.

The tatami-free lengths come in runs that get shorter as $b$ grows, and beyond some length every room with the same $a$ can be covered.

3. The left wall fixes the first column

The key lemma is due to Dean Hickerson: in a covering of an $a\times b$ room with $a\le b$, every horizontal mat that touches the left wall lies in the top row or in the bottom row. ^[2] ^[3] Ruskey and Woodcock prove it in full (Theorems 2.1 and 2.2); in outline, a staircase-shaped corner whose rows have lengths $1,2,\dots,h$ cannot be covered at all, because in a chessboard colouring it has $\lceil h/2\rceil$ more squares of one colour, while every mat covers one square of each colour. A horizontal mat at the left wall in a middle row forces further mats. If its row holds only horizontal mats, they form shorter and shorter staggered rows towards the nearer of the top and bottom walls; otherwise they form a diagonal that starts at the leftmost vertical mat of the row and runs to the top or bottom wall or to the right wall. In the last case they make up a slanted band of horizontal mats spanning all $b$ columns and $b-1$ rows, which cannot avoid both the top and the bottom row, since that would need $b-1\le a-2$. In every case such a corner is cut off.

Hence all squares of the first column except the top and bottom ones belong to vertical mats, which cover an even number of its squares. For odd $a$ the $a-2$ middle squares are an odd number, so exactly one corner square belongs to a horizontal mat; for even $a$, either both corner squares do or neither does.

4. Blocks of fixed width

The rest of a covering is forced almost completely. Take $a=5$, number the rows from the top, and put a horizontal mat in the bottom-left corner, so that the first column holds vertical mats on rows 1–2 and 3–4. The grid point between these two mats on the right edge of the column is a corner of both, so rows 2–3 of column 2 must hold one vertical mat, and rows 1 and 4 of column 2 can then only start horizontal mats. The first real choice concerns rows 2–3 of column 3: one vertical mat there completes a block of width $4$, while two horizontal mats force a block of width $6$. Either way the next column looks like the first one turned upside down, and the forcing starts again. In general, this is Hickerson's decomposition: ^[2] ^[3]

for odd $a\ge3$, every covering is a row of blocks of widths $a-1$ and $a+1$, and every sequence of such widths gives exactly two coverings, one for each choice of the first corner;
for even $a\ge4$, every covering is a row of blocks of widths $a-2$ and $a$, separated by single columns of vertical mats, with an optional column of vertical mats at either end, and every such sequence gives exactly one covering. The separating columns are forced: for $a=6$, a full column of vertical mats forces vertical mats on rows 2–3 and 4–5 of the next column, which starts a block, and the last column of a block, with vertical mats on rows 2–3 and 4–5, forces a full column of vertical mats after it.

For $a=7$ the block widths are $6$ and $8$. Hence $7\times8$ has $2$ coverings, $7\times12$ has $2$ (from $6+6$), $7\times14$ has $4$ (from $6+8$ and $8+6$), and $7\times10$ has none, because $10$ is not a sum of sixes and eights; that is why $7\times10$ is tatami-free. For $a=6$ the room $6\times12$ has the four coverings $1+4+1+6$, $1+6+1+4$, $4+1+6+1$ and $6+1+4+1$.

5. Which lengths can be built

Claim. A room $a\times b$ with $a\le b$ and $ab$ even can be covered if and only if there is an integer $k\ge1$ with

$$|b-ka|\le k+1.$$

Proof. A room with $a=1$ is one row of horizontal mats, and a room with $a=2$ can be filled with vertical mats side by side, where every inner grid point lies on a long side of a mat; both satisfy the inequality, with $k=b$ and with $k=\lceil b/2\rceil$. For $a\ge3$ we use Section 4 and let $k\ge1$ be the number of blocks of width close to $a$, $x$ of them narrow and $y$ wide.

Odd $a$: then $b=x(a-1)+y(a+1)$, that is, $b=ka+(y-x)$, where $y-x$ takes the values $-k,-k+2,\dots,k$. So $b$ can be built from $k$ blocks exactly when $|b-ka|\le k$ and $b-ka$ has the parity of $k$. Since $a$ is odd and $b$ is even, $b-ka\equiv k\pmod2$ always holds, and $|b-ka|=k+1$ is impossible for the same reason, so the condition is $|b-ka|\le k+1$.
Even $a$: with $k-1$ separating columns and $e\in\{0,1,2\}$ end columns, $b=x(a-2)+ya+(k-1)+e$, that is, $b=ka+(y-x)+(e-1)$. Here $y-x$ runs through $-k,-k+2,\dots,k$ and $e-1$ through $-1,0,1$, so $b-ka$ takes every integer value from $-k-1$ to $k+1$ and no other.

In both cases $k$ blocks produce exactly the lengths with $|b-ka|\le k+1$, which proves the claim.

6. The nearest multiple decides

The programs test a single value of $k$: the integer nearest to $b/a$, with halves rounded up,

$$g=\left\lfloor\frac{b+\lfloor a/2\rfloor}{a}\right\rfloor.$$

Claim. The room can be covered if and only if $|b-ga|\le g+1$.

Proof. Since $b\ge a$, we have $g\ge1$, so this condition is the one of Section 5 with $k=g$. Conversely, let $k\ge1$ satisfy $|b-ka|\le k+1$. The definition of $g$ gives

$$\begin{aligned}ga&\le b+\lfloor a/2\rfloor\lt(g+1)a,\\-\lfloor a/2\rfloor&\le b-ga\le\lceil a/2\rceil-1,\end{aligned}$$

so $|b-ga|\le\lfloor a/2\rfloor$, and $ga$ is a multiple of $a$ nearest to $b$; in particular $|b-ga|\le|b-ka|$. If $g\ge k$, then $|b-ga|\le k+1\le g+1$. If $g\lt k$, then $b\ge k(a-1)-1\ge(g+1)(a-1)-1$, so $b-ga\ge a-g-2$, and together with the upper bound above

$$g+1\ge a-\lceil a/2\rceil=\lfloor a/2\rfloor\ge|b-ga|.$$

For $7\times10$ we get $g=\lfloor13/7\rfloor=1$ and $|10-7|=3\gt2$, so the room is tatami-free. For $5\times14$ we get $g=\lfloor16/5\rfloor=3$ and $|14-15|=1\le4$; indeed blocks of widths $4$, $4$ and $6$ in their three orders give six coverings.

7. The gaps

The cases $a=1,2$ are already settled, so take $a\ge3$. By Section 5, the lengths that can be built form the intervals $[k(a-1)-1,\,k(a+1)+1]$ for $k\ge1$; for odd $a$ only their even members matter. The left ends of these intervals grow with $k$, and the first one starts at $a-2\lt a$. So the room is tatami-free exactly when $b$ falls strictly between two consecutive intervals, that is, when for some $k\ge1$

$$k(a+1)+2\le b\le(k+1)(a-1)-2.$$

For odd $a$ both bounds are even and the gap holds $(a-2k-3)/2$ even lengths; for even $a$ it holds $a-2k-4$ lengths. Three consequences follow.

Gaps exist only for $k\le(a-5)/2$, so every tatami-free room has $a\ge7$, and $7\times10$, the only length in the first gap of $a=7$, is the smallest one. Adding up the gaps, a short side $a\ge5$ has $(a-3)(a-5)/8$ tatami-free rooms if $a$ is odd and $(a-4)(a-6)/4$ if $a$ is even: $1,2,3,6,6,12,10,20$ rooms for $a=7,\dots,14$.
The last gap ends at $b=(a^2-4a-1)/2$ for odd $a\ge7$ and at $b=(a^2-5a)/2$ for even $a\ge8$, so always $b\lt a^2/2$. For odd $a$ this is Sylvester's formula in disguise: $b/2$ must be a sum of copies of the coprime numbers $p=(a-1)/2$ and $q=(a+1)/2$, the largest integer that is not such a sum is $pq-p-q$, ^[5] and its double is $(a^2-4a-1)/2$.
Since $s=ab\lt a^3/2$, only divisors $a\gt\sqrt[3]{2s}$ of $s$ can give tatami-free rooms.

8. Worked example: $T(70)$ and $T(1320)$

The rooms of size $70$ are $1\times70$, $2\times35$, $5\times14$ and $7\times10$. Only $a\gt\sqrt[3]{140}\approx5.2$ can fail, which leaves $a=7$; its first gap is $10\le b\le10$, and $b=10$ lies in it. So $T(70)=1$.

The size $1320=2^3\cdot3\cdot5\cdot11$ has $16$ rooms. Here $\sqrt[3]{2640}\approx13.8$ and $\sqrt{1320}\approx36.3$, so only the divisors $a=15,20,22,24,30,33$ between these bounds need a test:

$15\times88$: $g=\lfloor95/15\rfloor=6$ and $|88-90|=2\le7$, so the room can be covered;
$20\times66$: $g=3$, $|66-60|=6\gt4$, gap $65\le b\le74$ of $k=3$;
$22\times60$: $g=3$, $|60-66|=6\gt4$, gap $48\le b\le61$ of $k=2$;
$24\times55$: $g=2$, $|55-48|=7\gt3$, gap $52\le b\le67$ of $k=2$;
$30\times44$: $g=1$, $|44-30|=14\gt2$, gap $33\le b\le56$ of $k=1$;
$33\times40$: $g=1$, $|40-33|=7\gt2$, gap $36\le b\le62$ of $k=1$.

So $T(1320)=5$, with exactly the five rooms of the statement.

9. From a size to its rooms

Each room of size $s$ corresponds to one divisor $a\le\sqrt s$ of $s$, with $b=s/a$. If $s=p_1^{e_1}\cdots p_r^{e_r}$ is the prime factorisation, the divisors are the products $p_1^{f_1}\cdots p_r^{f_r}$ with $0\le f_i\le e_i$, so there are $\tau(s)=(e_1+1)\cdots(e_r+1)$ of them. ^[6] A depth-first search chooses $f_1$, then $f_2$, and so on, and abandons a partial product as soon as it exceeds $\sqrt s$, because the remaining primes can only make it larger. Every divisor $a\le\sqrt s$ is reached exactly once, since all its partial products are at most $a$. For $1320$ there are $(3+1)(1+1)(1+1)(1+1)=32$ divisors, and the search reaches exactly the $16$ of them that do not exceed $\lfloor\sqrt{1320}\rfloor=36$.

10. Searching for the smallest size

The problem considers only even sizes, so only even $s$ are examined. $T(s)$ does not grow steadily: the smallest sizes with $T(s)=1,2,\dots,12$ are $70$, $198$, $336$, $504$, $1320$, $1440$, $3696$, $3360$, $5040$, $8400$, $6720$ and $10080$; the seventh of these values exceeds the eighth, and the tenth exceeds the eleventh. Therefore the sizes must be examined in increasing order and the test must be $T(s)=200$ exactly; the first size with at least $200$ tatami-free rooms need not be the answer.

By Section 7, $T(s)$ counts only divisors in the narrow window $\sqrt[3]{2s}\lt a\le\sqrt s$, so a size with $200$ tatami-free rooms needs a very large number of divisors. The programs use this as a shortcut for the target $200$: they examine the multiples of $55440=2^4\cdot3^2\cdot5\cdot7\cdot11$, a highly composite number with $120$ divisors, ^[7] starting from $2\,051\,280=37\cdot55440$, the first multiple above $2\,000\,000$. This is a heuristic: nothing above proves that the smallest size with $T(s)=200$ is such a multiple, and the exhaustive check in the verification section settles this for the published result.

How the Code Works

The C++ program ^[9] reads the options --target=, --initial-limit= and --skip-checkpoints in parse_arguments, runs run_checkpoints unless told otherwise, and prints the result of find_smallest_size_with_t. The test of Section 6 is is_tatami_tileable: it orders the two sides, rejects an odd area, computes groups, which is $g$, as (b + a/2) / a and dist, which is $|ga-b|$, in 64-bit integers, and reports a covering exactly when dist does not exceed groups + 1. Its cache argument of SemigroupHelper records is ignored, and the helpers helper_for_m, mod_inverse, extended_gcd and representable_two_coin of a coin test with coins derived from the block widths (Section 7) are never executed.

build_spf is a linear sieve that stores the smallest prime factor of every number up to a limit, ^[8] and factorize divides by these factors to obtain the pairs $(p,e)$. count_tatami_free_rooms_for_size takes $\lfloor\sqrt s\rfloor$ from a long double square root and runs the search of Section 9 as a recursive lambda: the loop over the exponent of a prime stops once the partial product exceeds the root, and every leaf $a$ is tested with $b=s/a$. Its variant with the suffix _trial does the same after trial division by the primes from build_primes_simple, a sieve of Eratosthenes; a cofactor greater than $1$ left at the end is prime.

find_smallest_size_with_t has two paths. For the target $200$ it runs the stepped search of Section 10 over the multiples of $55440$ from $2\,051\,280$ up to $10^9$, the default hard_limit, with the $3401$ primes up to $31623$, and returns the first multiple whose count is $200$. For any other target, or if the stepped search finds nothing, it builds the factor table up to initial_limit, examines every even size up to that limit and keeps the smallest one whose count equals the target; failing that, it doubles the limit, rebuilds the table and scans again from $s=2$. run_checkpoints checks $T(70)=1$ and $T(1320)=5$ directly and, through the exhaustive path with the limits $200$ and $2000$, that the smallest sizes with $T(s)=1$ and $T(s)=5$ are $70$ and $1320$.

The Python and Java versions contain only the stepped search, with the target $200$, the same start and a cap of $2\cdot10^9$, and run no checkpoints. Their functions mirror the C++ ones, for example the trial-division count count_tatami_free_rooms or countTatamiFreeRooms with its dfs. Python takes the root from the exact math.isqrt and splits the multiples into consecutive chunks, each scanned upward to its first hit; the smallest of these hits is the first hit overall. Java walks through the same multiples and keeps the smallest hit. All sizes stay below $2^{31}$, so 32-bit integers hold $s$, $a$ and $b$; C++ and Java form the products $ag$ in 64 bits, and Python's integers are unbounded.

Complexity and Verification

For one size, factorisation costs $O(\log s)$ divisions with the factor table, or at most a few thousand trial divisions with the prime list ($3401$ primes in C++, $4648$ in Python and Java, fewer once the cofactor drops below the square of the next prime). The search of Section 9 visits at most $r+1$ nodes for each divisor $a\le\sqrt s$, at most $\tau(s)$ of them, and tests each such divisor in $O(1)$. The exhaustive path up to a limit $L$ therefore needs $O(L)$ time and memory for the factor table of $4(L+1)$ bytes and its list of primes, and $O(L\log L)$ time for the sizes, because $\sum_{n\le L}\tau(n)=L\ln L+O(L)$ and $r\le9$ for $s\lt2^{31}$. ^[6] The C++ stepped path counts the $(S-2\,051\,280)/55440+1$ multiples up to the size $S$ it returns; Python, which scans each chunk up to its own first hit, and Java, which skips only the multiples at or above its best hit so far, may also count multiples above $S$. On the computer used for this article every version finishes in at most about $0.2$ seconds.

The C++ checkpoints pass, and the three programs print the same value. For this article the following was also checked:

An exhaustive search over all coverings of every room with $a\le20$ and $a\le b\le a^2/2+a$, $1110$ rooms of even size of which $252$ are tatami-free, agrees with the criterion of Section 5 in every case; beyond $b=a^2/2$ no room is tatami-free by Section 7.
For the $98$ rooms with $3\le a\le10$ and $a\le b\le22$, backtracking and a column-by-column count both give the number of coverings predicted by the block decomposition. The column-by-column count also reproduces the whole table of coverings for $m,n\le16$ in ^[3] and confirms that the five tatami-free rooms of size $1320$ have no covering, while $15\times88$ has $30$.
The three forms of the criterion in Sections 5, 6 and 7 agree on all $1\,500\,500$ pairs $a\le b\le2000$ with $ab$ even, and the gap counts and last gaps of Section 7 hold for all $a\le200$.
An independent C++ program computed $T(s)$ for every even size up to well beyond the result, by running over all rooms with $b\lt a^2/2$ and applying the gap test of Section 7; its values agree with the published test, applied to all rooms, for every even $s\le2\cdot10^7$. Its first size with $T(s)=200$ is the value printed by the three programs, so the stepped search skipped no smaller solution, and six smaller sizes have more than $200$ tatami-free rooms, between $201$ and $209$. It also reproduces the table of Section 10, as does a separate Python scan.

Footnotes and References

The references below supply the background facts used above; the criterion of Section 5, its nearest-multiple form, the gap formula with its counts and the verification of the search are derived or checked in this article.

Project Euler 256 — Tatami-Free Rooms. The official statement defines the tatami rule, tatami-free rooms a × b with a ≤ b and even size s = ab, and the count T(s); it gives T(70) = 1 and T(1320) = 5 with the rooms involved, and asks for the smallest s with T(s) = 200.
Dean Hickerson — Filling rectangular rooms with Tatami mats (2002), a note attached to OEIS A068920, the table of the numbers of such coverings. The note proves that no horizontal mat touches the left edge except possibly in the top or bottom row and that, for odd r ≥ 3, the coverings of an r × s room consist of r × (r − 1) and r × (r + 1) blocks, two per composition of s; for even r ≥ 4 it states, leaving the details to the reader, that r × 1 blocks alternate with r × (r − 2) and r × r blocks, one covering per composition.
F. Ruskey and J. Woodcock — Counting Fixed-Height Tatami Tilings, Electronic Journal of Combinatorics 16 (2009), #R126. Theorems 2.1 and 2.2 show that the triangular corners of a rectangle cannot be tiled and prove the left-edge lemma for an m × n rectangle with m ≤ n, Theorems 2.3 and 2.4 present Hickerson's decomposition for odd m and for even m ≥ 4, and Table 2 lists the numbers of tatami tilings for m, n ≤ 16.
Wikipedia — Tatami. Tatami mats are twice as long as they are wide; in the auspicious layout the junctions of the mats form a T, while in the inauspicious grid layout they form a +.
Wikipedia — Coin problem. For two coprime denominations a₁ and a₂, the largest amount that cannot be formed is a₁a₂ − a₁ − a₂; J. J. Sylvester found this formula in 1882.
Wikipedia — Divisor function. The number of divisors of n is the product of the exponents in the prime factorisation of n, each increased by one, and by Dirichlet's estimate the numbers of divisors of all n ≤ x add up to x log x + (2γ − 1)x + O(√x).
OEIS A002182 — Highly composite numbers. The numbers whose number of divisors is larger than that of every smaller positive integer; 55440 is one of them.
cp-algorithms — Linear sieve computes the minimum prime factor of every number up to n in O(n) time, after which each of these numbers can be factorised by repeated division. Wikipedia — Sieve of Eratosthenes describes the classical sieve used for the list of primes, which marks the multiples of each prime p from p² on in O(n log log n) time.
C++ — Euler256.cpp. The linked immutable C++ revision contains is_tatami_tileable, count_tatami_free_rooms_for_size, find_smallest_size_with_t and run_checkpoints. It is the implementation record for this article.

Problem 256 source code

C++

#include <algorithm>
#include <array>
#include <atomic>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
#include <cmath>
#include <functional>
#include <thread>

namespace {

using i64 = long long;
using u64 = std::uint64_t;

struct Options {
    int target = 200;
    int initial_limit = 2'000'000;
    bool run_checkpoints = true;
};

struct SemigroupHelper {
    bool built = false;
    bool odd_case = false;
    i64 a = 0;
    i64 b = 0;
    i64 inv_a_mod_b = 0;
    std::array<i64, 6> shifts{};
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--target=", options.target) ||
            parse_int_after_prefix(arg, "--initial-limit=", options.initial_limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.target >= 1 && options.initial_limit >= 2;
}

i64 extended_gcd(i64 a, i64 b, i64& x, i64& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    i64 x1 = 0;
    i64 y1 = 0;
    const i64 g = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

i64 mod_inverse(i64 a, i64 mod) {
    i64 x = 0;
    i64 y = 0;
    const i64 g = extended_gcd(a, mod, x, y);
    if (g != 1) {
        return -1;
    }
    x %= mod;
    if (x < 0) {
        x += mod;
    }
    return x;
}

bool representable_two_coin(const i64 a, const i64 b, const i64 inv_a_mod_b, const i64 t) {
    if (t < 0) {
        return false;
    }
    const i64 x = ((t % b) * inv_a_mod_b) % b;
    return x * a <= t;
}

const SemigroupHelper& helper_for_m(const int m, std::vector<SemigroupHelper>& cache) {
    if (static_cast<int>(cache.size()) <= m) {
        cache.resize(static_cast<std::size_t>(m + 1));
    }

    SemigroupHelper& h = cache[static_cast<std::size_t>(m)];
    if (h.built) {
        return h;
    }

    h.built = true;
    if ((m & 1) != 0) {
        h.odd_case = true;
        h.a = (m - 1) / 2;
        h.b = (m + 1) / 2;
        h.inv_a_mod_b = mod_inverse(h.a, h.b);
    } else {
        h.odd_case = false;
        h.a = m - 1;
        h.b = m + 1;
        h.inv_a_mod_b = mod_inverse(h.a, h.b);
        h.shifts = {0, 1, m - 2, m - 1, m, m + 1};
    }

    return h;
}

bool is_tatami_tileable(int a, int b, std::vector<SemigroupHelper>& cache) {
    (void)cache;
    if (a > b) {
        std::swap(a, b);
    }

    if (((static_cast<i64>(a) * static_cast<i64>(b)) & 1LL) != 0) {
        return false;
    }

    const i64 groups = (static_cast<i64>(b) + (a / 2)) / static_cast<i64>(a);
    const i64 dist = std::llabs(static_cast<i64>(a) * groups - static_cast<i64>(b));
    return !(dist > groups + 1);
}

std::vector<int> build_spf(const int n) {
    std::vector<int> spf(static_cast<std::size_t>(n + 1), 0);
    std::vector<int> primes;
    primes.reserve(n / 10);

    for (int i = 2; i <= n; ++i) {
        if (spf[static_cast<std::size_t>(i)] == 0) {
            spf[static_cast<std::size_t>(i)] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            const i64 v = static_cast<i64>(i) * static_cast<i64>(p);
            if (v > n || p > spf[static_cast<std::size_t>(i)]) {
                break;
            }
            spf[static_cast<std::size_t>(v)] = p;
        }
    }
    if (n >= 1) {
        spf[1] = 1;
    }
    return spf;
}

std::vector<int> build_primes_simple(int n) {
    if (n < 2) {
        return {};
    }
    std::vector<std::uint8_t> is_prime(static_cast<std::size_t>(n + 1), 1U);
    is_prime[0] = is_prime[1] = 0U;
    for (int i = 2; static_cast<i64>(i) * i <= n; ++i) {
        if (!is_prime[static_cast<std::size_t>(i)]) {
            continue;
        }
        for (int j = i * i; j <= n; j += i) {
            is_prime[static_cast<std::size_t>(j)] = 0U;
        }
    }
    std::vector<int> primes;
    primes.reserve(n / 10);
    for (int i = 2; i <= n; ++i) {
        if (is_prime[static_cast<std::size_t>(i)]) {
            primes.push_back(i);
        }
    }
    return primes;
}

void factorize(int x, const std::vector<int>& spf, std::vector<std::pair<int, int>>& factors) {
    factors.clear();
    while (x > 1) {
        const int p = spf[static_cast<std::size_t>(x)];
        int e = 0;
        while (x % p == 0) {
            x /= p;
            ++e;
        }
        factors.push_back({p, e});
    }
}

int count_tatami_free_rooms_for_size(int s,
                                     const std::vector<int>& spf,
                                     std::vector<SemigroupHelper>& tileable_cache,
                                     std::vector<std::pair<int, int>>& factors) {
    factorize(s, spf, factors);

    const int root = static_cast<int>(std::sqrt(static_cast<long double>(s)));
    int count = 0;

    std::function<void(std::size_t, i64)> dfs = [&](std::size_t idx, i64 current) {
        if (idx == factors.size()) {
            if (current > root) {
                return;
            }
            const int a = static_cast<int>(current);
            const int b = s / a;
            if (!is_tatami_tileable(a, b, tileable_cache)) {
                ++count;
            }
            return;
        }

        const auto [p, e] = factors[idx];
        i64 value = current;
        for (int i = 0; i <= e; ++i) {
            if (value > root) {
                break;
            }
            dfs(idx + 1, value);
            value *= p;
        }
    };

    dfs(0, 1);
    return count;
}

int count_tatami_free_rooms_for_size_trial(
    int s, const std::vector<int>& primes, std::vector<SemigroupHelper>& tileable_cache) {
    std::vector<std::pair<int, int>> factors;
    factors.reserve(12);

    int x = s;
    for (int p : primes) {
        if (static_cast<i64>(p) * p > x) {
            break;
        }
        if (x % p != 0) {
            continue;
        }
        int e = 0;
        while (x % p == 0) {
            x /= p;
            ++e;
        }
        factors.push_back({p, e});
    }
    if (x > 1) {
        factors.push_back({x, 1});
    }

    const int root = static_cast<int>(std::sqrt(static_cast<long double>(s)));
    int count = 0;

    std::function<void(std::size_t, i64)> dfs = [&](std::size_t idx, i64 current) {
        if (idx == factors.size()) {
            if (current > root) {
                return;
            }
            const int a = static_cast<int>(current);
            const int b = s / a;
            if (!is_tatami_tileable(a, b, tileable_cache)) {
                ++count;
            }
            return;
        }

        const auto [p, e] = factors[idx];
        i64 value = current;
        for (int i = 0; i <= e; ++i) {
            if (value > root) {
                break;
            }
            dfs(idx + 1, value);
            value *= p;
        }
    };
    dfs(0, 1);

    return count;
}

int find_smallest_size_with_t(int target,
                              int initial_limit,
                              bool stop_if_not_found,
                              const int hard_limit = 1'000'000'000) {
    if (target == 200) {
        const int step = 55'440;
        const int start = std::max(step, ((std::max(2, initial_limit) + step - 1) / step) * step);
        const int fast_cap = std::min(hard_limit, 2'000'000'000);
        const std::vector<int> primes = build_primes_simple(
            static_cast<int>(std::sqrt(static_cast<long double>(fast_cap))) + 1);
        std::vector<SemigroupHelper> tileable_cache;

        for (int s = start; s <= fast_cap; s += step) {
            if ((s & 1) != 0) {
                continue;
            }
            if (count_tatami_free_rooms_for_size_trial(s, primes, tileable_cache) == target) {
                return s;
            }
        }
        if (stop_if_not_found) {
            return -1;
        }
    }

    int limit = std::max(2, initial_limit);

    while (limit <= hard_limit) {
        const std::vector<int> spf = build_spf(limit);
        unsigned threads = std::thread::hardware_concurrency();
        if (threads == 0) {
            threads = 4;
        }
        if (limit < 100'000) {
            threads = 1;
        }

        std::atomic<int> next_s{2};
        std::atomic<int> best{limit + 1};
        std::vector<std::thread> workers;
        workers.reserve(threads);

        for (unsigned tid = 0; tid < threads; ++tid) {
            workers.emplace_back([&]() {
                std::vector<SemigroupHelper> tileable_cache;
                std::vector<std::pair<int, int>> factors;
                factors.reserve(10);

                while (true) {
                    const int s = next_s.fetch_add(2, std::memory_order_relaxed);
                    if (s > limit) {
                        break;
                    }
                    if (s >= best.load(std::memory_order_relaxed)) {
                        continue;
                    }

                    const int t = count_tatami_free_rooms_for_size(s, spf, tileable_cache, factors);
                    if (t == target) {
                        int current = best.load(std::memory_order_relaxed);
                        while (s < current && !best.compare_exchange_weak(
                                                  current, s, std::memory_order_relaxed)) {
                        }
                    }
                }
            });
        }
        for (auto& th : workers) {
            th.join();
        }

        const int found = best.load(std::memory_order_relaxed);
        if (found <= limit) {
            return found;
        }

        if (stop_if_not_found) {
            return -1;
        }

        if (limit > hard_limit / 2) {
            break;
        }
        limit *= 2;
    }

    return -1;
}

bool run_checkpoints() {
    {
        const std::vector<int> spf = build_spf(70);
        std::vector<SemigroupHelper> tileable_cache;
        std::vector<std::pair<int, int>> factors;
        const int t70 = count_tatami_free_rooms_for_size(70, spf, tileable_cache, factors);
        if (t70 != 1) {
            std::cerr << "Checkpoint failed: T(70) should be 1, got " << t70 << '\n';
            return false;
        }
    }

    {
        const std::vector<int> spf = build_spf(1320);
        std::vector<SemigroupHelper> tileable_cache;
        std::vector<std::pair<int, int>> factors;
        const int t1320 = count_tatami_free_rooms_for_size(1320, spf, tileable_cache, factors);
        if (t1320 != 5) {
            std::cerr << "Checkpoint failed: T(1320) should be 5, got " << t1320 << '\n';
            return false;
        }
    }

    const int smallest_t1 = find_smallest_size_with_t(1, 200, true);
    if (smallest_t1 != 70) {
        std::cerr << "Checkpoint failed: smallest s with T(s)=1 should be 70, got " << smallest_t1
                  << '\n';
        return false;
    }

    const int smallest_t5 = find_smallest_size_with_t(5, 2000, true);
    if (smallest_t5 != 1320) {
        std::cerr << "Checkpoint failed: smallest s with T(s)=5 should be 1320, got " << smallest_t5
                  << '\n';
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    const int answer = find_smallest_size_with_t(options.target, options.initial_limit, false);
    if (answer < 0) {
        std::cerr << "No solution found within search bounds" << '\n';
        return 3;
    }

    std::cout << answer << '\n';
    return 0;
}

Python

import math
import multiprocessing

def is_tatami_tileable(a, b):
    if a > b:
        a, b = b, a
    if (a * b) % 2 != 0:
        return False
        
    groups = (b + a // 2) // a
    dist = abs(a * groups - b)
    return not (dist > groups + 1)

def build_primes_simple(n):
    if n < 2: return []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(math.isqrt(n)) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
                
    return [i for i, p in enumerate(is_prime) if p]

def count_tatami_free_rooms(s, primes):
    factors = []
    x = s
    for p in primes:
        if p * p > x: break
        if x % p != 0: continue
        e = 0
        while x % p == 0:
            x //= p
            e += 1
        factors.append((p, e))
    if x > 1:
        factors.append((x, 1))
        
    root = math.isqrt(s)
    count = [0]
    
    def dfs(idx, current):
        if idx == len(factors):
            if current <= root:
                a = current
                b = s // a
                if not is_tatami_tileable(a, b):
                    count[0] += 1
            return
            
        p, e = factors[idx]
        val = current
        for i in range(e + 1):
            if val > root: break
            dfs(idx + 1, val)
            val *= p
            
    dfs(0, 1)
    return count[0]

def worker(args):
    start, end, step, target, primes = args
    for s in range(start, end, step):
        if s % 2 != 0: continue
        if count_tatami_free_rooms(s, primes) == target:
            return s
    return float('inf')

def solve(target=200):
    step = 55440
    start = max(step, ((2000000 + step - 1) // step) * step)
    fast_cap = 2000000000
    
    primes = build_primes_simple(math.isqrt(fast_cap) + 1)
    
    threads = max(1, multiprocessing.cpu_count())
    total_steps = (fast_cap - start) // step + 1
    chunk = (total_steps + threads - 1) // threads
    
    tasks = []
    for t in range(threads):
        c_start = start + t * chunk * step
        c_end = min(fast_cap + 1, start + (t + 1) * chunk * step)
        if c_start < c_end:
            tasks.append((c_start, c_end, step, target, primes))
            
    best = float('inf')
    if threads > 1 and len(tasks) > 1:
        with multiprocessing.Pool(threads) as pool:
            for s in pool.imap_unordered(worker, tasks):
                if s < best:
                    best = s
    else:
        for t in tasks:
            s = worker(t)
            if s < best:
                best = s
                
    if best != float('inf'):
        return str(best)
    return "-1"

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

public class Euler256 {
    static boolean isTatamiTileable(int a, int b) {
        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }
        if (((long) a * b) % 2 != 0)
            return false;
        long groups = (b + a / 2) / a;
        long dist = Math.abs(a * groups - b);
        return !(dist > groups + 1);
    }

    static List<Integer> buildPrimesSimple(int n) {
        if (n < 2)
            return new ArrayList<>();
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; (long) i * i <= n; ++i) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; ++i) {
            if (isPrime[i])
                primes.add(i);
        }
        return primes;
    }

    static class Factor {
        int p, e;

        Factor(int p, int e) {
            this.p = p;
            this.e = e;
        }
    }

    static int countTatamiFreeRooms(int s, List<Integer> primes) {
        List<Factor> factors = new ArrayList<>();
        int x = s;
        for (int p : primes) {
            if ((long) p * p > x)
                break;
            if (x % p != 0)
                continue;
            int e = 0;
            while (x % p == 0) {
                x /= p;
                e++;
            }
            factors.add(new Factor(p, e));
        }
        if (x > 1) {
            factors.add(new Factor(x, 1));
        }

        int root = (int) Math.sqrt(s);
        int[] count = new int[] { 0 };

        dfs(0, 1, factors, root, s, count);
        return count[0];
    }

    static void dfs(int idx, long current, List<Factor> factors, int root, int s, int[] count) {
        if (idx == factors.size()) {
            if (current <= root) {
                int a = (int) current;
                int b = s / a;
                if (!isTatamiTileable(a, b)) {
                    count[0]++;
                }
            }
            return;
        }

        Factor f = factors.get(idx);
        long val = current;
        for (int i = 0; i <= f.e; ++i) {
            if (val > root)
                break;
            dfs(idx + 1, val, factors, root, s, count);
            val *= f.p;
        }
    }

    public static String solve() {
        int target = 200;
        int step = 55440;
        int initialLimit = 2000000;
        int start = Math.max(step, ((initialLimit + step - 1) / step) * step);
        int fastCap = 2000000000;

        List<Integer> primes = buildPrimesSimple((int) Math.sqrt(fastCap) + 1);

        int threads = Math.max(1, Runtime.getRuntime().availableProcessors());
        ExecutorService executor = Executors.newFixedThreadPool(threads);
        AtomicInteger nextS = new AtomicInteger(start);
        AtomicInteger best = new AtomicInteger(Integer.MAX_VALUE);

        List<Future<?>> futures = new ArrayList<>();

        for (int t = 0; t < threads; ++t) {
            futures.add(executor.submit(() -> {
                while (true) {
                    int s = nextS.getAndAdd(step);
                    if (s > fastCap)
                        break;
                    if (s >= best.get())
                        continue;
                    if (s % 2 != 0)
                        continue;

                    if (countTatamiFreeRooms(s, primes) == target) {
                        int current = best.get();
                        while (s < current && !best.compareAndSet(current, s)) {
                            current = best.get();
                        }
                    }
                }
            }));
        }

        for (Future<?> f : futures) {
            try {
                f.get();
            } catch (Exception e) {
            }
        }
        executor.shutdown();

        if (best.get() != Integer.MAX_VALUE) {
            return String.valueOf(best.get());
        }
        return "-1";
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}