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.
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.
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.
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.$$
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.
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\).
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\).
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.
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\).
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.
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\).
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.
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.
Für eine zulässige Fläche \(s\) ist jede Raumform genau ein Teilerpaar \((a,b)\) mit
$$ab=s,\qquad a\le b.$$
Die Implementierung definiert \(T(s)\) als die Anzahl derjenigen Rechtecke, die den im Solver verwendeten Tatami-Test nicht bestehen. Gesucht ist das kleinste \(s\) mit
$$T(s)=\text{Zielwert}.$$
Im vollständigen Euler-Problem ist \(\text{Zielwert}=200\). Der endgültige Zahlenwert wird hier absichtlich nicht ausgeschrieben.
Sobald die Fläche \(s\) fest ist, bleibt keine kontinuierliche Geometrie mehr übrig: Jeder Kandidat wird durch einen Teiler \(a\) von \(s\) bestimmt, und die zweite Seite ist \(b=s/a\).
Daher gilt
$$T(s)=\sum_{\substack{a\mid s\\a\le \sqrt{s}}}\mathbf{1}_{\neg \mathrm{tileable}(a,s/a)}.$$
Die Bedingung \(a\le \sqrt{s}\) sorgt dafür, dass jedes ungeordnete Paar genau einmal gezählt wird. Damit wird das ganze Problem zu einer Divisor-Aufzählung mit einem arithmetischen Test pro Paar.
Der Solver erhöht \(s\) immer um 2 und testet keine ungeraden Flächen. Das passt zur im Code kodierten Raumklasse: Der Prädikatstest verwirft ungerade Flächen sofort, also kann die Suche von Anfang an auf gerade \(s\) eingeschränkt werden.
Diese Beobachtung halbiert den äußeren Suchraum. Danach bleibt die eigentliche Arbeit: für ein gerades \(s\) schnell zu zählen, wie viele Teilerpaare den Tatami-Test nicht bestehen.
Nach dem Sortieren der Seiten zu \(a\le b\) verwendet is_tatami_tileable genau die folgende Regel.
Ist \(ab\) ungerade, liefert die Funktion sofort false.
Andernfalls berechnet sie
$$g=\left\lfloor\frac{b+\lfloor a/2\rfloor}{a}\right\rfloor,$$
und
$$d=\lvert ag-b\rvert.$$
Das Rechteck gilt genau dann als kachelbar, wenn
$$d\le g+1.$$
Ein Paar trägt also genau dann zu \(T(s)\) bei, wenn
$$d>g+1.$$
Schreibe
$$b=qa+r,\qquad 0\le r<a.$$
Dann wählt \(g\) dasjenige Vielfache von \(a\), das \(b\) am nächsten liegt. Genauer:
$$g=\begin{cases} q, & r<\lceil a/2\rceil,\\ q+1, & r\ge \lceil a/2\rceil, \end{cases}$$
und damit
$$d=\begin{cases} r, & r<\lceil a/2\rceil,\\ a-r, & r\ge \lceil a/2\rceil. \end{cases}$$
Also ist \(d\) schlicht der Abstand von \(b\) zum nächstliegenden Vielfachen von \(a\). Der Code erklärt ein Rechteck genau dann als tatami-frei, wenn dieser Abstand größer als \(g+1\) ist.
Ein eingebauter Checkpoint lautet
$$T(70)=1.$$
Die Teilerpaare von 70 sind
$$ (1,70),\ (2,35),\ (5,14),\ (7,10). $$
Für \((5,14)\) gilt
$$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,$$
also besteht dieses Rechteck den Test.
Für \((7,10)\) dagegen gilt
$$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.$$
Somit ist \((7,10)\) das einzige tatami-freie Paar und daher \(T(70)=1\).
Der Code überprüft außerdem
$$T(1320)=5.$$
Die Paare mit \(a\le \sqrt{1320}\) sind
$$ (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). $$
Genau die folgenden fünf scheitern:
$$ (20,66),\ (22,60),\ (24,55),\ (30,44),\ (33,40). $$
Zum Beispiel liefert \((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,$$
also einen Fehlfall. Dagegen besteht \((15,88)\), denn
$$g=\left\lfloor\frac{88+7}{15}\right\rfloor=6,\qquad d=\lvert 15\cdot 6-88\rvert=2\le 7.$$
Daher ist \(T(1320)=5\).
Um ein einzelnes \(s\) effizient zu testen, braucht man eine schnelle Divisor-Erzeugung. Ist
$$s=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},$$
dann hat jeder Teiler die Form
$$a=p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k},\qquad 0\le f_i\le e_i.$$
factorize bestimmt diese Primfaktoren im allgemeinen Suchpfad mit einer SPF-Tabelle und im schnellen Schrittpfad per Probedivision über vorab erzeugte Primzahlen. Danach erzeugt eine Tiefensuche über die Exponenten \(f_i\) alle Teiler.
Die Rekursion bricht ab, sobald der aktuelle Teiler größer als \(\sqrt{s}\) wird. Dann wäre der Komplementfaktor kleiner und das Rechteck bereits in umgekehrter Reihenfolge gezählt.
Jedes ungeordnete Rechteck der Fläche \(s\) besitzt genau eine kleinere Seite \(a\le \sqrt{s}\). Umgekehrt bestimmt jeder Teiler \(a\le \sqrt{s}\) genau ein Paar \((a,s/a)\).
Die DFS in count_tatami_free_rooms_for_size ist daher eine exakte Aufzählung aller Kandidaten und keine Heuristik.
Gesucht ist nicht nur \(T(s)\) für ein festes \(s\), sondern das kleinste \(s\), bei dem \(T(s)\) den Zielwert erreicht.
Für allgemeine Zielwerte führt der Code eine vollständige gerade Suche aus: Er baut eine SPF-Tabelle bis zu einer Grenze auf, verteilt gerade Werte von \(s\) auf mehrere Threads und speichert den kleinsten Treffer in einer atomaren Variable.
Wird nichts gefunden, verdoppelt sich die Grenze und der Vorgang startet erneut.
Für das spezielle Euler-Ziel 200 probiert die Implementierung zuerst einen schnelleren Heuristikpfad über Vielfache von
$$55440=2^4\cdot 3^2\cdot 5\cdot 7\cdot 11.$$
Das ist keine mathematische Notwendigkeit, sondern eine Optimierung: Vielfache eines so teilerreichen Schritts sind natürliche Kandidaten, wenn man große Werte von \(T(s)\) erwartet. Falls dieser Schnellpfad nicht reicht, folgt die vollständige Suche.
Der Quelltext überprüft vier Kontrollwerte:
$$T(70)=1,\qquad T(1320)=5,$$
und außerdem
$$\min\{s:T(s)=1\}=70,\qquad \min\{s:T(s)=5\}=1320.$$
Damit werden sowohl die lokale Divisorzählung als auch die globale Suche nach dem ersten gültigen \(s\) abgesichert.
build_spf(limit) erzeugt die Tabelle der kleinsten Primfaktoren. Für eine Kandidatenfläche \(s\) faktorisiert count_tatami_free_rooms_for_size die Zahl, erzeugt per DFS alle Divisoren bis \(\sqrt{s}\), bildet jedes Paar \((a,b)\) und prüft es mit is_tatami_tileable. Die äußere Routine find_smallest_size_with_t scannt gerade Werte von \(s\), parallelisiert die Arbeit über Threads und liefert die kleinste Fläche mit dem gewünschten Zählergebnis zurück.
Der Sonderfall target == 200 nutzt zuerst die Schrittweite 55440 mit Probedivision und fällt erst danach auf die allgemeine Methode zurück. Die Lösung verbindet also exakte Arithmetik mit pragmatischer Suchoptimierung.
Für eine feste Fläche \(s\) ist der dominante mathematische Aufwand die Divisor-Erzeugung. Nach der Faktorisierung ist die Arbeit proportional zur Anzahl der erzeugten Teiler, also
$$O(\tau(s)),$$
wobei \(\tau(s)\) die Teilerfunktion ist. Mit SPF-Unterstützung ist die Faktorisierung selbst sehr schnell, sodass die praktische Kostenformel ungefähr lautet: „zerlegen und alle Teilerpaare testen“.
Liegt die erste Lösung bei \(S^\ast\), dann untersucht die vollständige Suche alle geraden \(s\le S^\ast\). Die Gesamtlaufzeit ist also näherungsweise die Summe dieser Einzelkosten über den Suchbereich. Der Speicherverbrauch wird von der SPF-Tabelle bis zur aktuellen Grenze dominiert und ist daher linear in der Suchgrenze. Multithreading verbessert die Wandzeit, nicht aber die asymptotische Anzahl der Tests.
Uygun bir \(s\) alanı için her oda şekli,
$$ab=s,\qquad a\le b$$
koşulunu sağlayan bir \((a,b)\) bölen çiftidir. Uygulama, çözücünün kullandığı tatami testini geçemeyen bu dikdörtgenlerin sayısını \(T(s)\) olarak tanımlar. Amaç,
$$T(s)=\text{hedef}$$
eşitliğini sağlayan en küçük \(s\)'yi bulmaktır. Tam Project Euler probleminde \(\text{hedef}=200\) alınır. Nihai sayısal cevap burada özellikle verilmez.
\(s\) sabitlendikten sonra artık sürekli bir geometri araması kalmaz: Her aday oda, \(s\)'nin bir böleni \(a\) ile belirlenir ve diğer kenar otomatik olarak \(b=s/a\) olur.
Dolayısıyla
$$T(s)=\sum_{\substack{a\mid s\\a\le \sqrt{s}}}\mathbf{1}_{\neg \mathrm{tileable}(a,s/a)}.$$
\(a\le \sqrt{s}\) koşulu, sırasız her kenar çiftinin tam bir kez sayılmasını sağlar. Böylece bütün problem, her \(s\) için bölen çiftlerini üretip bunlara koddaki aritmetik testi uygulamaya dönüşür.
Çözücü \(s\) değerini 2'şer artırır ve tek alanları hiç denemez. Bu, kodun kullandığı oda modeline uygundur: test yordamı tek alanı doğrudan reddeder. Bu yüzden arama uzayı en baştan çift \(s\) değerlerine indirgenir.
Bu tek gözlem dış aramayı yarıya indirir. Bundan sonraki zor kısım, bir çift \(s\) için kaç bölen çiftinin tatami koşulunu bozduğunu hızlı saymaktır.
Kenarlar \(a\le b\) olacak şekilde sıralandıktan sonra is_tatami_tileable fonksiyonu şu kuralı uygular.
Eğer \(ab\) tek ise fonksiyon hemen false döndürür.
Aksi halde
$$g=\left\lfloor\frac{b+\lfloor a/2\rfloor}{a}\right\rfloor,$$
ve
$$d=\lvert ag-b\rvert$$
hesaplanır. Oda tam olarak şu durumda döşenebilir kabul edilir:
$$d\le g+1.$$
Bu yüzden bir bölen çifti ancak şu durumda \(T(s)\)'ye katkı yapar:
$$d>g+1.$$
Şöyle yazalım:
$$b=qa+r,\qquad 0\le r<a.$$
Bu durumda \(g\), \(b\)'ye en yakın \(a\) katını seçen tam sayıdır. Daha açık yazarsak
$$g=\begin{cases} q, & r<\lceil a/2\rceil,\\ q+1, & r\ge \lceil a/2\rceil, \end{cases}$$
ve dolayısıyla
$$d=\begin{cases} r, & r<\lceil a/2\rceil,\\ a-r, & r\ge \lceil a/2\rceil. \end{cases}$$
Yani \(d\), \(b\)'nin en yakın \(a\) katına olan uzaklığıdır. Kod, bu sapma \(g+1\)'den büyükse odayı tatami-free sayar.
Uygulamadaki kontrol noktalarından biri
$$T(70)=1$$
eşitliğidir. 70'in bölen çiftleri
$$ (1,70),\ (2,35),\ (5,14),\ (7,10) $$
şeklindedir. \((5,14)\) için
$$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,$$
olduğundan bu oda testi geçer.
Fakat \((7,10)\) için
$$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.$$
Dolayısıyla yalnızca \((7,10)\) çifti başarısız olur ve sonuç olarak \(T(70)=1\) elde edilir.
Kod ayrıca
$$T(1320)=5$$
değerini de doğrular. \(a\le \sqrt{1320}\) için bölen çiftleri
$$ (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) $$
olur. Başarısız olanlar tam olarak şunlardır:
$$ (20,66),\ (22,60),\ (24,55),\ (30,44),\ (33,40). $$
Örneğin \((20,66)\) için
$$g=\left\lfloor\frac{66+10}{20}\right\rfloor=3,\qquad d=\lvert 20\cdot 3-66\rvert=6,\qquad 6>4=g+1,$$
yani bu çift başarısızdır. Buna karşılık \((15,88)\) çifti
$$g=\left\lfloor\frac{88+7}{15}\right\rfloor=6,\qquad d=\lvert 15\cdot 6-88\rvert=2\le 7$$
olduğu için geçer. Böylece tam beş başarısız çift vardır ve \(T(1320)=5\) olur.
Tek bir \(s\) değerini verimli test etmek için bölenleri hızlı üretmek gerekir. Eğer
$$s=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$$
ise, her bölen
$$a=p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k},\qquad 0\le f_i\le e_i$$
şeklindedir. Genel arama yolunda factorize bunu SPF tablosuyla çıkarır; hızlı adım yolunda ise önceden üretilmiş asallarla deneme bölmesi kullanılır. Sonra üsler üzerinde yapılan bir DFS tüm bölenleri üretir.
DFS, ara bölen \(\sqrt{s}\)'yi geçtiği anda durur. Çünkü o noktadan sonra tamamlayıcı bölen daha küçük olur ve aynı dikdörtgen ters sırayla zaten sayılmış olur.
Alanı \(s\) olan her sırasız dikdörtgenin tek bir küçük kenarı vardır ve bu kenar \(a\le \sqrt{s}\) koşulunu sağlar. Tersine, \(a\le \sqrt{s}\) olan her bölen de tam bir \((a,s/a)\) dikdörtgeni üretir.
Bu nedenle count_tatami_free_rooms_for_size içindeki DFS yaklaşık bir yöntem değildir; aday odaların tam sayımıdır.
Asıl amaç yalnızca tek bir \(s\) için \(T(s)\)'yi bulmak değil, \(T(s)\) hedefe eşit olduğunda en küçük \(s\)'yi yakalamaktır.
Genel hedeflerde kod kapsamlı bir çift sayı taraması yapar: belli bir sınıra kadar SPF tablosu kurulur, çift \(s\) değerleri iş parçacıklarına dağıtılır ve bulunan en küçük uygun değer atomik bir değişkende tutulur.
Bulunamazsa sınır iki katına çıkarılır ve süreç tekrarlanır.
Project Euler'daki özel hedef olan 200 için uygulama önce şu sayının katları üzerinde daha hızlı bir sezgisel tarama yapar:
$$55440=2^4\cdot 3^2\cdot 5\cdot 7\cdot 11.$$
Bu matematiksel bir zorunluluk değildir; bir optimizasyondur. Bölen bakımından zengin böyle bir adımın katları, \(T(s)\)'nin büyük olmasını beklediğimiz doğal adaylardır. Bu hızlı yol sonuç vermezse program tam çift taramasına geri döner.
Kaynak kod dört temel kontrol kullanır:
$$T(70)=1,\qquad T(1320)=5,$$
ve ayrıca
$$\min\{s:T(s)=1\}=70,\qquad \min\{s:T(s)=5\}=1320.$$
Bunlar çözümün iki katmanını birlikte doğrular: yerel bölen çifti sayımı ve ilk uygun \(s\)'yi bulan dış arama.
build_spf(limit) en küçük asal çarpan tablosunu üretir. Her aday alan \(s\) için count_tatami_free_rooms_for_size sayıyı çarpanlarına ayırır, \(\sqrt{s}\)'ye kadar tüm bölenleri DFS ile üretir, her \((a,b)\) çiftini oluşturur ve is_tatami_tileable ile test eder. Dıştaki find_smallest_size_with_t yordamı çift \(s\) değerlerini tarar, işi iş parçacıklarına böler ve hedef sayıya ulaşan en küçük alanı döndürür.
target == 200 özel yolu önce 55440 adımlı hızlı taramayı kullanır, sonra gerekirse genel yönteme döner. Yani çözüm hem tam aritmetik teste hem de pratik arama mühendisliğine dayanır.
Sabit bir \(s\) için baskın maliyet bölen üretimidir. Çarpanlara ayırmadan sonra iş yükü üretilen bölen sayısıyla orantılıdır:
$$O(\tau(s)).$$
Burada \(\tau(s)\) bölen sayısı fonksiyonudur. SPF ile çarpanlara ayırma çok hızlı olduğundan, pratikte bir adayın maliyeti yaklaşık olarak “çarpanlara ayır ve tüm bölen çiftlerini test et” biçimindedir.
İlk çözüm \(S^\ast\) noktasında çıkıyorsa, tam arama \(S^\ast\)'ye kadar bütün çift \(s\) değerlerini inceler. Dolayısıyla toplam süre bu aralıktaki aday maliyetlerinin toplamıdır. Bellek kullanımı esas olarak mevcut sınıra kadar tutulan SPF tablosundan gelir ve arama sınırına göre lineerdir. Çok iş parçacıklı çalışma duvar süresini azaltır, ama asimptotik test sayısını değiştirmez.
Para un area admisible \(s\), cada forma de habitacion corresponde a un par de factores \((a,b)\) tal que
$$ab=s,\qquad a\le b.$$
La implementacion define \(T(s)\) como el numero de esos rectangulos que no superan la prueba aritmetica de tatami usada por el solucionador. Se busca el menor \(s\) que cumpla
$$T(s)=\text{objetivo}.$$
En el problema completo de Project Euler se toma \(\text{objetivo}=200\). El valor final se omite aqui a proposito.
Una vez fijada el area \(s\), ya no hay una busqueda geometrica continua: cada habitacion candidata queda determinada por un divisor \(a\) de \(s\), y el otro lado es \(b=s/a\).
Por tanto,
$$T(s)=\sum_{\substack{a\mid s\\a\le \sqrt{s}}}\mathbf{1}_{\neg \mathrm{tileable}(a,s/a)}.$$
La restriccion \(a\le \sqrt{s}\) asegura que cada par no ordenado se cuente exactamente una vez. Toda la tarea se reduce entonces a enumerar pares de divisores y aplicarles el criterio aritmetico del codigo.
El solucionador incrementa \(s\) de dos en dos y nunca prueba areas impares. Eso coincide con el modelo de habitaciones usado por la implementacion: el predicado rechaza inmediatamente un area impar, de modo que el espacio de busqueda se reduce a valores pares desde el principio.
Esa observacion divide por dos la exploracion global. El verdadero trabajo esta en contar rapidamente, para cada \(s\) par, cuantos pares de divisores fallan la condicion tatami.
Despues de ordenar los lados como \(a\le b\), la funcion is_tatami_tileable aplica exactamente la siguiente regla.
Si \(ab\) es impar, devuelve false de inmediato.
Si no, calcula
$$g=\left\lfloor\frac{b+\lfloor a/2\rfloor}{a}\right\rfloor,$$
y
$$d=\lvert ag-b\rvert.$$
El rectangulo se considera teselable exactamente cuando
$$d\le g+1.$$
Por lo tanto, un par contribuye a \(T(s)\) precisamente cuando
$$d>g+1.$$
Escribamos
$$b=qa+r,\qquad 0\le r<a.$$
Entonces \(g\) selecciona el multiplo de \(a\) mas cercano a \(b\). En forma explicita,
$$g=\begin{cases} q, & r<\lceil a/2\rceil,\\ q+1, & r\ge \lceil a/2\rceil, \end{cases}$$
y por consiguiente
$$d=\begin{cases} r, & r<\lceil a/2\rceil,\\ a-r, & r\ge \lceil a/2\rceil. \end{cases}$$
Asi, \(d\) es simplemente la distancia de \(b\) al multiplo de \(a\) mas cercano. El codigo declara la habitacion tatami-free cuando esa discrepancia es mayor que \(g+1\).
Uno de los puntos de control incorporados es
$$T(70)=1.$$
Los pares de divisores de 70 son
$$ (1,70),\ (2,35),\ (5,14),\ (7,10). $$
Para \((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,$$
de modo que ese rectangulo pasa.
En cambio, para \((7,10)\),
$$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.$$
Por tanto, \((7,10)\) es el unico par tatami-free y \(T(70)=1\).
El codigo tambien verifica que
$$T(1320)=5.$$
Los pares con \(a\le \sqrt{1320}\) son
$$ (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). $$
Los que fallan son exactamente
$$ (20,66),\ (22,60),\ (24,55),\ (30,44),\ (33,40). $$
Por ejemplo, para \((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,$$
asi que falla. En cambio \((15,88)\) pasa porque
$$g=\left\lfloor\frac{88+7}{15}\right\rfloor=6,\qquad d=\lvert 15\cdot 6-88\rvert=2\le 7.$$
Por eso hay exactamente cinco pares no teselables y \(T(1320)=5\).
Para probar un valor \(s\) con eficiencia se necesita generar sus divisores rapidamente. Si
$$s=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},$$
entonces cada divisor es de la forma
$$a=p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k},\qquad 0\le f_i\le e_i.$$
La funcion factorize obtiene esos factores primos mediante una tabla SPF en la busqueda general, o mediante division por primos precalculados en la pasada rapida por saltos. Despues, una DFS sobre los exponentes \(f_i\) genera todos los divisores.
La recursion se detiene cuando el divisor parcial ya supera \(\sqrt{s}\). En ese punto el factor complementario seria menor y el mismo rectangulo ya habria aparecido al reves.
Cada rectangulo no ordenado de area \(s\) tiene un lado menor unico \(a\le \sqrt{s}\). Y a la inversa, cada divisor \(a\le \sqrt{s}\) determina exactamente un par \((a,s/a)\).
Por eso la recursion de count_tatami_free_rooms_for_size no es heuristica: es una enumeracion exacta de todas las habitaciones candidatas.
El objetivo completo no es evaluar un solo \(s\), sino encontrar el menor \(s\) para el que \(T(s)\) alcanza el objetivo.
Para objetivos generales, el codigo hace una busqueda exhaustiva sobre valores pares: construye una tabla SPF hasta cierto limite, reparte los \(s\) pares entre varios hilos y guarda el menor acierto encontrado en una variable atomica.
Si no aparece solucion, el limite se duplica y el proceso se repite.
Para el objetivo Euler especifico \(200\), la implementacion intenta primero una pasada heuristica mas rapida sobre multiplos de
$$55440=2^4\cdot 3^2\cdot 5\cdot 7\cdot 11.$$
Eso no es una necesidad matematica, sino una optimizacion. Los multiplos de un paso tan rico en divisores son candidatos naturales cuando se espera que \(T(s)\) sea grande. Si esa pasada no basta, el programa vuelve a la exploracion completa.
El codigo fuente valida cuatro hechos:
$$T(70)=1,\qquad T(1320)=5,$$
y ademas
$$\min\{s:T(s)=1\}=70,\qquad \min\{s:T(s)=5\}=1320.$$
Estos controles verifican tanto el contador local de pares de divisores como la busqueda global del primer \(s\) valido.
build_spf(limit) construye la tabla del menor factor primo. Para cada area candidata \(s\), la rutina count_tatami_free_rooms_for_size factoriza \(s\), ejecuta la DFS de divisores hasta \(\sqrt{s}\), forma cada par \((a,b)\) y lo prueba con is_tatami_tileable. La rutina exterior find_smallest_size_with_t recorre los valores pares de \(s\), paraleliza el trabajo entre hilos y devuelve la menor area cuyo conteo coincide con el objetivo.
La ruta especial para target == 200 usa primero candidatos separados por 55440 y solo despues cae en el metodo general. En consecuencia, la solucion mezcla un test aritmetico exacto con una estrategia de busqueda practica.
Para un area fija \(s\), el costo matematico dominante es la generacion de divisores. Tras factorizar, el trabajo es proporcional al numero de divisores generados, es decir
$$O(\tau(s)),$$
donde \(\tau(s)\) es la funcion que cuenta divisores. Con apoyo de SPF, la propia factorizacion es muy rapida, asi que el costo practico por candidato es aproximadamente "factorizar y probar todos los pares de divisores".
Si la primera solucion aparece en \(S^\ast\), la busqueda exhaustiva revisa todos los \(s\) pares hasta \(S^\ast\). El tiempo total es aproximadamente la suma de esos costos locales en todo el rango. La memoria esta dominada por la tabla SPF hasta el limite actual y por eso es lineal en la cota de busqueda. El paralelismo mejora el tiempo real, pero no cambia el numero asintotico de pruebas.
对一个允许的面积 \(s\)，每一种房间形状都对应一个因子对 \((a,b)\)，满足
$$ab=s,\qquad a\le b.$$
实现中把没有通过求解器所用 tatami 判定的这些矩形个数记作 \(T(s)\)。目标是找到最小的 \(s\)，使得
$$T(s)=\text{target}.$$
在完整的 Project Euler 问题中，\(\text{target}=200\)。最终数值答案在这里有意省略。
一旦面积 \(s\) 固定，就不再需要连续几何搜索了：每一个候选房间都由 \(s\) 的一个约数 \(a\) 决定，另一条边自动是 \(b=s/a\)。
因此
$$T(s)=\sum_{\substack{a\mid s\\a\le \sqrt{s}}}\mathbf{1}_{\neg \mathrm{tileable}(a,s/a)}.$$
\(a\le \sqrt{s}\) 的限制保证每个无序边长对只统计一次。所以整个问题变成：枚举 \(s\) 的约数对，并对每一对应用代码中的算术判定。
求解器每次把 \(s\) 增加 2，从不检查奇数面积。这与实现所编码的房间模型一致：判定函数会立即拒绝奇数面积，因此搜索空间从一开始就缩小为偶数 \(s\)。
这个观察直接把外层搜索减半。真正的难点在于：对每个偶数 \(s\)，怎样快速数出有多少约数对会失败。
把边长整理成 \(a\le b\) 之后，is_tatami_tileable 使用的规则非常直接。
如果 \(ab\) 为奇数，函数立刻返回 false。
否则计算
$$g=\left\lfloor\frac{b+\lfloor a/2\rfloor}{a}\right\rfloor,$$
以及
$$d=\lvert ag-b\rvert.$$
当且仅当
$$d\le g+1$$
时，矩形被判定为可铺。于是一个约数对会计入 \(T(s)\) 的条件正是
$$d>g+1.$$
把 \(b\) 写成
$$b=qa+r,\qquad 0\le r<a.$$
那么 \(g\) 就是在选取最接近 \(b\) 的那个 \(a\) 的倍数。更具体地说，
$$g=\begin{cases} q, & r<\lceil a/2\rceil,\\ q+1, & r\ge \lceil a/2\rceil, \end{cases}$$
从而
$$d=\begin{cases} r, & r<\lceil a/2\rceil,\\ a-r, & r\ge \lceil a/2\rceil. \end{cases}$$
所以 \(d\) 本质上就是 \(b\) 到最近的 \(a\) 的倍数之间的距离。代码规定：如果这个偏差大于 \(g+1\)，那么该房间就是 tatami-free。
实现中的一个检查点是
$$T(70)=1.$$
70 的约数对为
$$ (1,70),\ (2,35),\ (5,14),\ (7,10). $$
对 \((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,$$
因此它通过测试。
而对 \((7,10)\)，
$$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.$$
所以只有 \((7,10)\) 失败，故 \(T(70)=1\)。
代码还验证了
$$T(1320)=5.$$
满足 \(a\le \sqrt{1320}\) 的约数对为
$$ (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). $$
其中失败的恰好是
$$ (20,66),\ (22,60),\ (24,55),\ (30,44),\ (33,40). $$
例如对 \((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,$$
因此失败。相反，\((15,88)\) 通过，因为
$$g=\left\lfloor\frac{88+7}{15}\right\rfloor=6,\qquad d=\lvert 15\cdot 6-88\rvert=2\le 7.$$
于是失败的正好有 5 对，所以 \(T(1320)=5\)。
要高效测试某个 \(s\)，就必须快速生成它的约数。若
$$s=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},$$
则每个约数都可写成
$$a=p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k},\qquad 0\le f_i\le e_i.$$
在一般搜索路径中，factorize 借助 SPF 表得到这些质因子；在快速步进路径中，则使用预先生成的质数表做试除。之后，对指数 \(f_i\) 做一次 DFS，就能生成全部约数。
当当前部分约数已经大于 \(\sqrt{s}\) 时，递归立即停止。因为这时互补因子会更小，而对应矩形已经以相反顺序被统计过了。
面积为 \(s\) 的每个无序矩形都有唯一一个较小边，它满足 \(a\le \sqrt{s}\)。反过来，每个满足 \(a\le \sqrt{s}\) 的约数又唯一决定一个矩形 \((a,s/a)\)。
因此 count_tatami_free_rooms_for_size 中的 DFS 不是近似，也不是抽样，而是对所有候选房间的精确枚举。
完整任务不是只算某个固定 \(s\) 的 \(T(s)\)，而是找到使 \(T(s)\) 达到目标值的最小 \(s\)。
对于一般目标，代码执行完全的偶数扫描：先构建到某个上界的 SPF 表，再把偶数 \(s\) 分配给多个线程，并用原子变量保存目前找到的最小命中值。
如果没有找到答案，就把上界翻倍，再重复这一过程。
对于 Euler 题中的特殊目标 200，程序会先尝试一个更快的启发式路径，只检查
$$55440=2^4\cdot 3^2\cdot 5\cdot 7\cdot 11$$
的倍数。这不是数学上的必要条件，而是工程优化：这样一个约数很丰富的步长，它的倍数更可能产生较大的 \(T(s)\)。如果这条快速路径没有成功，程序就回退到完整扫描。
源代码内置了四个重要检查：
$$T(70)=1,\qquad T(1320)=5,$$
以及
$$\min\{s:T(s)=1\}=70,\qquad \min\{s:T(s)=5\}=1320.$$
这些检查同时验证了两个层面：局部的约数对计数，以及全局上“最小满足条件的 \(s\)”搜索。
build_spf(limit) 构造最小质因子表。对每个候选面积 \(s\)，函数 count_tatami_free_rooms_for_size 先分解 \(s\)，再用 DFS 枚举到 \(\sqrt{s}\) 为止的所有约数，形成每个 \((a,b)\) 对，并调用 is_tatami_tileable 测试。外层函数 find_smallest_size_with_t 扫描偶数 \(s\)，用多线程并行处理，并返回第一个满足目标计数的面积。
当 target == 200 时，程序先走 55440 步长的快速路径，再在需要时回到通用方法。因此，这份实现既有精确的算术判定，也有现实可用的搜索优化。
对于固定的一个面积 \(s\)，主要数学开销是约数枚举。完成分解后，工作量与生成出的约数数量成正比，即
$$O(\tau(s)),$$
其中 \(\tau(s)\) 是约数个数函数。由于有 SPF 支持，分解本身很快，所以单个候选值的实际代价可以近似看成“分解一次，再测试所有约数对”。
如果第一个解出现在 \(S^\ast\)，那么完全扫描会检查所有不超过 \(S^\ast\) 的偶数 \(s\)。总时间大致就是这一范围内各个局部成本的总和。内存主要由当前上界以内的 SPF 表占用，因此与搜索上界线性相关。多线程可以改善实际运行时间，但不会改变渐近测试次数。
Для допустимой площади \(s\) каждая форма комнаты задается парой делителей \((a,b)\), где
$$ab=s,\qquad a\le b.$$
Реализация определяет \(T(s)\) как число тех прямоугольников, которые не проходят tatami-проверку, используемую решателем. Нужно найти наименьшее \(s\), для которого
$$T(s)=\text{target}.$$
В полной задаче Project Euler берется \(\text{target}=200\). Сам численный ответ здесь намеренно не приводится.
Как только площадь \(s\) фиксирована, никакого непрерывного геометрического поиска уже нет: каждая кандидатная комната задается делителем \(a\) числа \(s\), а вторая сторона равна \(b=s/a\).
Поэтому
$$T(s)=\sum_{\substack{a\mid s\\a\le \sqrt{s}}}\mathbf{1}_{\neg \mathrm{tileable}(a,s/a)}.$$
Ограничение \(a\le \sqrt{s}\) гарантирует, что каждая неупорядоченная пара считается ровно один раз. Значит, вся задача сводится к перечислению пар делителей и применению к каждой паре арифметического критерия из кода.
Решатель увеличивает \(s\) на 2 и не проверяет нечетные площади. Это соответствует модели, зашитой в реализации: предикат сразу отвергает нечетную площадь, поэтому пространство поиска изначально сокращается до четных \(s\).
Это наблюдение сразу уменьшает внешний перебор вдвое. Дальше главная трудность состоит в том, чтобы быстро посчитать, сколько пар делителей у данного четного \(s\) нарушают tatami-критерий.
После упорядочивания сторон так, чтобы \(a\le b\), функция is_tatami_tileable применяет ровно следующее правило.
Если \(ab\) нечетно, она немедленно возвращает false.
Иначе вычисляются
$$g=\left\lfloor\frac{b+\lfloor a/2\rfloor}{a}\right\rfloor,$$
и
$$d=\lvert ag-b\rvert.$$
Прямоугольник считается замощаемым тогда и только тогда, когда
$$d\le g+1.$$
Следовательно, вклад в \(T(s)\) дает именно случай
$$d>g+1.$$
Запишем
$$b=qa+r,\qquad 0\le r<a.$$
Тогда \(g\) выбирает тот множитель \(a\), чей кратный член ближе всего к \(b\). Более точно,
$$g=\begin{cases} q, & r<\lceil a/2\rceil,\\ q+1, & r\ge \lceil a/2\rceil, \end{cases}$$
и потому
$$d=\begin{cases} r, & r<\lceil a/2\rceil,\\ a-r, & r\ge \lceil a/2\rceil. \end{cases}$$
Итак, \(d\) - это расстояние от \(b\) до ближайшего кратного числа \(a\). Код объявляет комнату tatami-free, если это отклонение больше, чем \(g+1\).
Одна из встроенных проверок такова:
$$T(70)=1.$$
Пары делителей числа 70 равны
$$ (1,70),\ (2,35),\ (5,14),\ (7,10). $$
Для \((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,$$
поэтому эта комната проходит тест.
А вот для \((7,10)\)
$$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.$$
Значит, только пара \((7,10)\) является tatami-free, и потому \(T(70)=1\).
Код также проверяет, что
$$T(1320)=5.$$
Пары с \(a\le \sqrt{1320}\) таковы:
$$ (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). $$
Из них не проходят ровно следующие:
$$ (20,66),\ (22,60),\ (24,55),\ (30,44),\ (33,40). $$
Например, для \((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,$$
поэтому пара отвергается. А \((15,88)\) проходит, поскольку
$$g=\left\lfloor\frac{88+7}{15}\right\rfloor=6,\qquad d=\lvert 15\cdot 6-88\rvert=2\le 7.$$
Следовательно, число tatami-free пар равно 5, то есть \(T(1320)=5\).
Чтобы эффективно проверить одно значение \(s\), нужно быстро перечислить его делители. Если
$$s=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},$$
то любой делитель имеет вид
$$a=p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k},\qquad 0\le f_i\le e_i.$$
Функция factorize получает это разложение либо через таблицу SPF в общем поисковом режиме, либо через пробное деление по заранее построенному списку простых чисел в быстром режиме. Затем DFS по показателям \(f_i\) порождает все делители.
Рекурсия останавливается, как только текущий частичный делитель превышает \(\sqrt{s}\). После этого дополнительный множитель уже будет меньше, а значит соответствующий прямоугольник был учтен раньше в обратном порядке.
У каждого неупорядоченного прямоугольника площади \(s\) есть единственная меньшая сторона \(a\le \sqrt{s}\). И наоборот, каждый делитель \(a\le \sqrt{s}\) однозначно задает пару \((a,s/a)\).
Поэтому DFS в count_tatami_free_rooms_for_size - это точное перечисление всех кандидатов, а не эвристика.
Полная задача состоит не в вычислении \(T(s)\) для одного заданного \(s\), а в поиске минимального \(s\), для которого \(T(s)\) достигает цели.
Для общих целей код выполняет полный перебор четных \(s\): строит таблицу SPF до текущего лимита, распределяет четные значения между потоками и хранит наименьшее найденное решение в атомарной переменной.
Если решение не найдено, лимит удваивается, и процесс повторяется.
Для специальной цели Euler, равной 200, реализация сначала пробует более быстрый эвристический проход по кратным числам
$$55440=2^4\cdot 3^2\cdot 5\cdot 7\cdot 11.$$
Это не математическая необходимость, а оптимизация. Кратные столь богатого делителями шага являются естественными кандидатами, если ожидается большое значение \(T(s)\). Если быстрый проход не помогает, программа возвращается к полному перебору.
Исходник проверяет четыре факта:
$$T(70)=1,\qquad T(1320)=5,$$
а также
$$\min\{s:T(s)=1\}=70,\qquad \min\{s:T(s)=5\}=1320.$$
Эти проверки подтверждают обе части решения: локальный подсчет пар делителей и глобальный поиск первого подходящего \(s\).
build_spf(limit) строит таблицу наименьших простых делителей. Для каждой кандидатной площади \(s\) функция count_tatami_free_rooms_for_size раскладывает число, запускает DFS по делителям до \(\sqrt{s}\), формирует пары \((a,b)\) и применяет к ним is_tatami_tileable. Внешняя функция find_smallest_size_with_t перебирает четные значения \(s\), распараллеливает работу по потокам и возвращает минимальную площадь с нужным счетчиком.
Специальная ветка для target == 200 сначала использует быстрый проход с шагом 55440, а затем при необходимости переходит к общему методу. Тем самым решение сочетает точную арифметику и практичную организацию поиска.
Для фиксированной площади \(s\) основная математическая стоимость - это перечисление делителей. После факторизации работа пропорциональна числу сгенерированных делителей, то есть
$$O(\tau(s)),$$
где \(\tau(s)\) - функция числа делителей. Благодаря SPF сама факторизация очень быстра, поэтому практическая стоимость одного кандидата примерно равна "разложить и проверить все пары делителей".
Если первое решение встречается в точке \(S^\ast\), то полный поиск просматривает все четные \(s\le S^\ast\). Общее время примерно равно сумме этих локальных затрат на всем диапазоне. Память определяется прежде всего таблицей SPF до текущего лимита, то есть линейна по поисковой границе. Многопоточность уменьшает реальное время, но не меняет асимптотическое число проверок.
لكل مساحة مسموح بها \(s\)، فإن كل شكل غرفة يقابل زوج قواسم \((a,b)\) يحقق
$$ab=s,\qquad a\le b.$$
وتعرّف الشيفرة \(T(s)\) على أنها عدد هذه المستطيلات التي تفشل في اختبار tatami الحسابي المستخدم في الحل. المطلوب إيجاد أصغر \(s\) تحقق
$$T(s)=\text{الهدف}.$$
وفي مسألة Project Euler الكاملة يكون \(\text{الهدف}=200\). أمّا الجواب العددي النهائي فمقصود عدم عرضه هنا.
بمجرد تثبيت المساحة \(s\)، لا تبقى أي عملية بحث هندسي مستمرة: كل غرفة مرشحة تحددها قيمة قاسم \(a\) للعدد \(s\)، ثم يكون الضلع الآخر مباشرة هو \(b=s/a\).
لذلك
$$T(s)=\sum_{\substack{a\mid s\\a\le \sqrt{s}}}\mathbf{1}_{\neg \mathrm{tileable}(a,s/a)}.$$
والشرط \(a\le \sqrt{s}\) يضمن أن كل زوج غير مرتب يُحسب مرة واحدة فقط. وهكذا تصبح المسألة كلها هي: ولّد أزواج القواسم ثم طبّق عليها الشرط الحسابي الموجود في الكود.
الحل يزيد \(s\) بمقدار 2 في كل مرة ولا يفحص المساحات الفردية. وهذا يطابق نموذج الغرف الموجود في التنفيذ: دالة الاختبار ترفض المساحة الفردية فورًا، لذلك يضيق فضاء البحث منذ البداية إلى القيم الزوجية فقط.
هذه الملاحظة وحدها تختصر البحث الخارجي إلى النصف. بعد ذلك تصبح المهمة الحقيقية هي عدّ أزواج القواسم التي تفشل شرط tatami بسرعة لكل \(s\) زوجي.
بعد ترتيب الضلعين بحيث \(a\le b\)، تطبق الدالة is_tatami_tileable القاعدة التالية حرفيًا.
إذا كان \(ab\) فرديًا فإنها تعيد false مباشرة.
وإلا فهي تحسب
$$g=\left\lfloor\frac{b+\lfloor a/2\rfloor}{a}\right\rfloor,$$
ثم
$$d=\lvert ag-b\rvert.$$
ويُعد المستطيل قابلاً للتبليط تمامًا عندما
$$d\le g+1.$$
وبالتالي فإن زوج القواسم يساهم في \(T(s)\) بالضبط عندما
$$d>g+1.$$
لنكتب
$$b=qa+r,\qquad 0\le r<a.$$
عندها يكون \(g\) هو العدد الصحيح الذي يختار المضاعف الأقرب لـ \(a\) إلى القيمة \(b\). وبصورة أدق
$$g=\begin{cases} q, & r<\lceil a/2\rceil,\\ q+1, & r\ge \lceil a/2\rceil, \end{cases}$$
ومن ثم
$$d=\begin{cases} r, & r<\lceil a/2\rceil,\\ a-r, & r\ge \lceil a/2\rceil. \end{cases}$$
إذًا فإن \(d\) ليس إلا المسافة بين \(b\) وأقرب مضاعف لـ \(a\). ويعتبر الكود الغرفة tatami-free عندما يكون هذا الانحراف أكبر من \(g+1\).
إحدى نقاط التحقق داخل التنفيذ هي
$$T(70)=1.$$
وأزواج القواسم للعدد 70 هي
$$ (1,70),\ (2,35),\ (5,14),\ (7,10). $$
بالنسبة إلى \((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,$$
إذن هذا المستطيل ينجح.
أما بالنسبة إلى \((7,10)\) فنجد
$$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.$$
وبذلك يكون الزوج \((7,10)\) هو الوحيد الذي يفشل، ومن ثم \(T(70)=1\).
تتحقق الشيفرة أيضًا من أن
$$T(1320)=5.$$
وأزواج القواسم التي تحقق \(a\le \sqrt{1320}\) هي
$$ (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). $$
والأزواج الفاشلة بالضبط هي
$$ (20,66),\ (22,60),\ (24,55),\ (30,44),\ (33,40). $$
فمثلًا عند \((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,$$
ولذلك يفشل. في المقابل ينجح الزوج \((15,88)\) لأن
$$g=\left\lfloor\frac{88+7}{15}\right\rfloor=6,\qquad d=\lvert 15\cdot 6-88\rvert=2\le 7.$$
إذن يوجد خمسة أزواج tatami-free تمامًا، أي \(T(1320)=5\).
لكي نختبر قيمة واحدة من \(s\) بكفاءة، نحتاج إلى توليد قواسمها بسرعة. إذا كان
$$s=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},$$
فإن كل قاسم يكتب على الصورة
$$a=p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k},\qquad 0\le f_i\le e_i.$$
تستخرج الدالة factorize هذا التحليل باستعمال جدول SPF في المسار العام، أو باستعمال القسمة التجريبية على قائمة أعداد أولية في المسار السريع. بعد ذلك تولد DFS على الأسس \(f_i\) جميع القواسم.
ويتوقف التفرع عندما يصبح القاسم الجزئي أكبر من \(\sqrt{s}\). عندها يكون القاسم المتمم أصغر، أي إن المستطيل المقابل قد عُدّ مسبقًا بترتيب معكوس.
لكل مستطيل غير مرتب مساحته \(s\) ضلع أصغر وحيد يحقق \(a\le \sqrt{s}\). وبالعكس، كل قاسم يحقق \(a\le \sqrt{s}\) يحدد زوجًا واحدًا فقط هو \((a,s/a)\).
لهذا فإن DFS داخل count_tatami_free_rooms_for_size ليست تقريبًا ولا عينة، بل تعدادًا دقيقًا لجميع الغرف المرشحة.
الهدف الكامل ليس حساب \(T(s)\) لقيمة واحدة من \(s\)، بل إيجاد أصغر \(s\) تصل فيها \(T(s)\) إلى الهدف المطلوب.
بالنسبة إلى الأهداف العامة، ينفذ الكود مسحًا كاملًا على القيم الزوجية: يبني جدول SPF حتى حد معين، ويوزع قيم \(s\) الزوجية على الخيوط، ويحفظ أصغر إصابة في متغير ذري.
وإذا لم تظهر نتيجة، يتضاعف الحد وتبدأ العملية من جديد.
أما في حالة هدف Euler الخاص وهو 200، فإن التنفيذ يجرب أولًا مسارًا أسرع يعتمد على مضاعفات
$$55440=2^4\cdot 3^2\cdot 5\cdot 7\cdot 11.$$
وهذا ليس ضرورة رياضية، بل تحسين عملي. فمضاعفات خطوة غنية بالقواسم بهذا الشكل هي مرشحات طبيعية عندما نتوقع أن تكون \(T(s)\) كبيرة. وإذا لم ينجح هذا المسار السريع، يعود البرنامج إلى المسح الكامل.
يتحقق المصدر من أربع حقائق:
$$T(70)=1,\qquad T(1320)=5,$$
وكذلك
$$\min\{s:T(s)=1\}=70,\qquad \min\{s:T(s)=5\}=1320.$$
وهذه الفحوص تثبت شقّي الحل معًا: عدّ أزواج القواسم محليًا، والبحث عن أول \(s\) يحقق الشرط عالميًا.
تبني الدالة build_spf(limit) جدول أصغر عامل أولي. ولكل مساحة مرشحة \(s\)، تقوم الدالة count_tatami_free_rooms_for_size بتحليل \(s\)، ثم تشغيل DFS لتوليد جميع القواسم حتى \(\sqrt{s}\)، ثم تشكيل كل زوج \((a,b)\) واختباره عبر is_tatami_tileable. أما الدالة الخارجية find_smallest_size_with_t فتمسح القيم الزوجية لـ \(s\)، وتوزع العمل على الخيوط، ثم تعيد أصغر مساحة يساوي فيها العد الهدف المطلوب.
وفي الحالة الخاصة target == 200 يستخدم البرنامج أولًا المسار السريع بخطوة 55440 ثم يعود عند الحاجة إلى الطريقة العامة. لذلك يجمع الحل بين اختبار حسابي دقيق وهندسة بحث عملية.
بالنسبة إلى قيمة ثابتة من \(s\)، فإن الكلفة الرياضية الأساسية هي توليد القواسم. وبعد التحليل إلى عوامل أولية يصبح الجهد متناسبًا مع عدد القواسم المولدة، أي
$$O(\tau(s)),$$
حيث \(\tau(s)\) هي دالة عدد القواسم. وبوجود SPF يكون التحليل نفسه سريعًا جدًا، لذلك يمكن وصف كلفة المرشح الواحد عمليًا بأنها "حلل ثم اختبر جميع أزواج القواسم".
إذا ظهر أول حل عند \(S^\ast\)، فإن المسح الكامل يمر على كل القيم الزوجية حتى \(S^\ast\). لذا فإن الزمن الكلي يقارب مجموع هذه الكلف المحلية على كامل المجال. أما الذاكرة فتسيطر عليها أساسًا بنية SPF حتى الحد الحالي، ولذلك فهي خطية في حد البحث. وتفيد الخيوط في تقليل الزمن الفعلي، لكنها لا تغير العدد التقاربي للاختبارات.