Problem 256: Tatami-Free Rooms
View on Project EulerProject 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
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. The difficult part is then no longer parity, but efficiently counting how many divisor pairs of an even \(s\) fail the tatami criterion.
3. The Exact Arithmetic Tatami Test Used by the Code
After ordering the sides so that \(a\le b\), the function is_tatami_tileable applies the following rule.
If \(ab\) is odd, the function returns false immediately.
Otherwise it computes
$$g=\left\lfloor\frac{b+\lfloor a/2\rfloor}{a}\right\rfloor,$$
and
$$d=\lvert ag-b\rvert.$$
The room is declared tileable exactly when
$$d\le g+1.$$
So a divisor pair contributes to \(T(s)\) precisely when
$$d>g+1.$$
4. Interpreting \(g\) and \(d\)
Write
$$b=qa+r,\qquad 0\le r<a.$$
Then the quantity \(g\) is the integer that chooses the multiple of \(a\) closest to \(b\) (with the usual upward choice at exact halves when \(a\) is even). More explicitly,
$$g=\begin{cases} q, & r<\lceil a/2\rceil,\\ q+1, & r\ge \lceil a/2\rceil, \end{cases}$$
and therefore
$$d=\begin{cases} r, & r<\lceil a/2\rceil,\\ a-r, & r\ge \lceil a/2\rceil. \end{cases}$$
So \(d\) is simply the distance from \(b\) to the nearest multiple of \(a\). The code says the room is tatami-tileable if this mismatch is at most \(g+1\), and tatami-free if it is larger.
5. Worked Example: \(T(70)=1\)
The implementation checks the checkpoint
$$T(70)=1.$$
The divisor pairs of 70 are
$$ (1,70),\ (2,35),\ (5,14),\ (7,10). $$
For \((5,14)\),
$$g=\left\lfloor\frac{14+\lfloor 5/2\rfloor}{5}\right\rfloor=\left\lfloor\frac{16}{5}\right\rfloor=3,$$
$$d=\lvert 5\cdot 3-14\rvert=1\le 4,$$
so that room passes.
For \((7,10)\), however,
$$g=\left\lfloor\frac{10+\lfloor 7/2\rfloor}{7}\right\rfloor=\left\lfloor\frac{13}{7}\right\rfloor=1,$$
$$d=\lvert 7\cdot 1-10\rvert=3>2=g+1.$$
Thus \((7,10)\) is the only tatami-free factor pair, so \(T(70)=1\).
6. Second Checkpoint: \(T(1320)=5\)
The code also verifies
$$T(1320)=5.$$
The divisor pairs with \(a\le \sqrt{1320}\) are
$$ (1,1320),(2,660),(3,440),(4,330),(5,264),(6,220),(8,165),(10,132),(11,120),(12,110),(15,88),(20,66),(22,60),(24,55),(30,44),(33,40). $$
The failing ones are exactly
$$ (20,66),\ (22,60),\ (24,55),\ (30,44),\ (33,40). $$
For instance, for \((20,66)\),
$$g=\left\lfloor\frac{66+10}{20}\right\rfloor=3,\qquad d=\lvert 20\cdot 3-66\rvert=6,\qquad 6>4=g+1,$$
so it fails. By contrast, \((15,88)\) passes because
$$g=\left\lfloor\frac{88+7}{15}\right\rfloor=6,\qquad d=\lvert 15\cdot 6-88\rvert=2\le 7.$$
Hence exactly five divisor pairs are tatami-free, giving \(T(1320)=5\).
7. Factorization and Divisor Generation
Testing one area \(s\) efficiently requires fast divisor enumeration. If
$$s=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},$$
then every divisor has the form
$$a=p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k},\qquad 0\le f_i\le e_i.$$
The function factorize obtains the prime powers using an SPF table in the general search, or a prime list during the fast stepped search. Then a DFS over the exponents \(f_i\) generates all divisors.
The DFS stops whenever the partial divisor already exceeds \(\sqrt{s}\). This matters because once \(a>\sqrt{s}\), the complementary factor \(b=s/a\) would satisfy \(b<a\), so that pair has already been counted in reversed order.
8. Why the Divisor DFS Counts Every Room Exactly Once
Every unordered rectangle with area \(s\) has a unique smaller side \(a\le \sqrt{s}\). Conversely, every divisor \(a\le \sqrt{s}\) determines exactly one rectangle \((a,s/a)\).
So the recursion in count_tatami_free_rooms_for_size is not an approximation and not a sampling step. It is an exact enumeration of all candidate rooms of area \(s\).
9. Global Search Strategy
The full goal is not to evaluate one fixed \(s\), but to find the smallest \(s\) for which \(T(s)\) hits the target.
For general targets, the code performs an exhaustive even scan: it builds an SPF table up to some limit, distributes even values of \(s\) across worker threads, and keeps the smallest hit found so far in an atomic variable.
If nothing is found, the limit is doubled and the process repeats.
For the specific Euler target \(200\), the implementation first tries a faster heuristic pass over multiples of
$$55440=2^4\cdot 3^2\cdot 5\cdot 7\cdot 11.$$
This is not a logical necessity of the mathematics; it is an optimization. Multiples of such a divisor-rich step are natural places to look first when one wants \(T(s)\) to be large. If that fast pass does not solve the problem, the program falls back to the full even scan.
10. Checkpoints for Correctness
The source validates itself with four checkpoints:
$$T(70)=1,\qquad T(1320)=5,$$
and the smallest searched sizes satisfy
$$\min\{s:T(s)=1\}=70,\qquad \min\{s:T(s)=5\}=1320.$$
These checks verify both layers of the solution: the local divisor-pair counter and the global search for the first valid \(s\).
How the Code Works
The helper build_spf(limit) constructs the smallest-prime-factor table. For each candidate area \(s\), the function count_tatami_free_rooms_for_size factors \(s\), runs the divisor DFS, forms each pair \((a,b)\), and applies is_tatami_tileable. The outer routine find_smallest_size_with_t scans even values of \(s\), parallelizes the work across threads, and returns the first area whose count equals the requested target.
The special path for target == 200 uses trial division on stepped candidates before the general fallback. So the implementation combines exact arithmetic testing with practical search engineering.
Complexity Analysis
For one fixed area \(s\), the dominant mathematical cost is divisor enumeration. After factorization, the work is proportional to the number of generated divisors, namely
$$O(\tau(s)),$$
where \(\tau(s)\) is the divisor-counting function. With SPF support, factorization itself is very fast, so per candidate the practical cost is roughly “factorize plus test all divisor pairs”.
If the first valid answer is \(S^\ast\), then the exhaustive search examines even \(s\le S^\ast\), so the total running time is roughly the sum of these per-\(s\) costs over that range. The memory usage is dominated by the SPF table up to the current limit, hence linear in the search bound. Multithreading improves wall-clock time but not the asymptotic count of arithmetic tests.
Footnotes and References
- Problem page: https://projecteuler.net/problem=256
- Divisor function and divisor counting: Wikipedia - Divisor function
- Smallest prime factor / linear sieve idea: cp-algorithms - Linear sieve
- Prime factorization and divisor generation: cp-algorithms - Integer factorization
- Floor and rounding notation: Wikipedia - Floor and ceiling functions
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());
}
}