For each integer \(k\), let \(M(k)\) be the smallest rectangle area that has exactly \(k\) manufacturable variants. A variant is an admissible factor pair \((x,y)\) with \(x\le y\), both sides manufacturable, and
$$10y\le 11x,$$
so the rectangle is within \(10\%\) of a square. The required answer is
$$\sum_{k=2}^{100} M(k).$$
The implementations encode the manufacturing rule through admissible side lengths: a positive integer side is manufacturable exactly when all of its prime factors belong to \(\{2,3,5,7,11,13,17,19,23\}\).
Let
$$P=\{2,3,5,7,11,13,17,19,23\}$$
and define the manufacturable side set
$$\mathcal{S}=\left\{n\in \mathbb{Z}_{>0}: \text{every prime divisor of } n \text{ lies in } P\right\}.$$
For any area \(A\), define its admissible multiplicity by
$$r(A)=\#\left\{(x,y)\in \mathcal{S}^2 : x\le y,\ xy=A,\ 10y\le 11x\right\}.$$
Then
$$M(k)=\min\{A:r(A)=k\}.$$
The allowed rescalings only introduce prime factors at most \(23\). Conversely, every prime in \(P\) is itself an allowed multiplier, so repeated valid rescalings can build any positive integer whose prime divisors all lie in \(P\).
Therefore the manufacturable side lengths are exactly the \(23\)-smooth positive integers. This converts the original manufacturing constraint into a clean number-theoretic set \(\mathcal{S}\).
After ordering the sides so that \(x\le y\), every rectangle variant corresponds to one factorization \(A=xy\) with
$$x\le y,\qquad 10y\le 11x.$$
The inequality forces the two factors to lie close to \(\sqrt{A}\), and the condition \(x\le y\) removes the reflected duplicate \((y,x)\).
Because products of \(23\)-smooth numbers are still \(23\)-smooth, every admissible area is itself \(23\)-smooth. Also, every divisor of a \(23\)-smooth number is again \(23\)-smooth, so once an area \(A\) is fixed, counting manufacturable variants is the same as counting admissible divisor pairs of \(A\) near its square root.
The function \(r(A)\) records how many admissible near-square factorizations produce the same area. Different areas can have the same multiplicity, and \(M(k)\) selects the smallest area with multiplicity exactly \(k\).
So the whole problem becomes
$$\sum_{k=2}^{100} M(k).$$
This viewpoint separates the task into two layers: enumerate all relevant side lengths, then aggregate areas by the number of admissible factor pairs that generate them.
Suppose we only enumerate side lengths up to some cap \(L\). Let \(r_L(A)\) be the same count as \(r(A)\), but restricted to pairs with \(x,y\le L\). As \(L\) grows, the set of visible pairs only increases, so \(r_L(A)\) is monotone.
Now consider any admissible pair with area \(A\). Since \(x\le y\) and \(xy=A\), we have \(x\le \sqrt{A}\le y\). Combining this with \(10y\le 11x\) gives
$$y\le \frac{11}{10}x\le \frac{11}{10}\sqrt{A}.$$
Hence every admissible pair for area \(A\) is guaranteed to be visible once
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{A}\right\rceil \right\rceil.$$
If all needed values \(M(2),\dots,M(100)\) have already been found and this inequality also holds for
$$A=\max_{2\le k\le 100} M(k),$$
then no unseen pair can alter any relevant minimum, so the search is finished.
The implementations verify the checkpoint
$$M(3)=889200.$$
For this area, the admissible factor pairs are
$$ (900,988),\qquad (912,975),\qquad (936,950). $$
Each pair satisfies \(x\le y\), each product is \(889200\), and each ratio \(y/x\) is below \(1.1\). Every side is also \(23\)-smooth:
$$\begin{aligned} 900&=2^2\cdot 3^2\cdot 5^2, & 988&=2^2\cdot 13\cdot 19,\\ 912&=2^4\cdot 3\cdot 19, & 975&=3\cdot 5^2\cdot 13,\\ 936&=2^3\cdot 3^2\cdot 13, & 950&=2\cdot 5^2\cdot 19. \end{aligned}$$
Therefore \(r(889200)=3\), and this area is the first one with multiplicity \(3\).
The C++, Python, and Java implementations start from a moderate side cap and recursively generate every \(23\)-smooth side length up to that cap. The list is then sorted and deduplicated so each manufacturable side is processed once.
Next, the implementation scans the sorted side list with \(x\le y\). For each shorter side \(x\), it only considers longer sides up to \(\left\lfloor \frac{11x}{10}\right\rfloor\), because larger values would violate the near-square rule. Each admissible pair contributes one count to its area \(A=xy\). After all pairs are processed, the smallest area for each multiplicity \(k\in[2,100]\) is extracted from the area-count table.
If some \(M(k)\) is still missing, the side cap is multiplied by \(10\) and the process repeats. Once every \(M(k)\) from \(2\) through \(100\) has appeared, the implementation checks the coverage bound
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{\max_k M(k)}\right\rceil \right\rceil$$
to prove that no admissible pair for any relevant area lies beyond the current cap. At that point the final sum is returned.
Let \(s(L)\) be the number of \(23\)-smooth integers up to the final cap \(L\). Generating the smooth numbers is output-sensitive; after sorting and deduplication it costs \(O(s(L)\log s(L))\) time and \(O(s(L))\) memory.
The pair scan is worst-case \(O(s(L)^2)\), although the constraint \(10y\le 11x\) keeps only a narrow band near the diagonal and makes the practical workload much smaller. The area-count table uses linear memory in the number of distinct admissible areas encountered. Because the cap grows geometrically, the last successful round dominates the total runtime.
Für jede ganze Zahl \(k\) sei \(M(k)\) die kleinste Rechtecksfläche mit genau \(k\) herstellbaren Varianten. Eine Variante ist ein zulässiges Faktorenpaar \((x,y)\) mit \(x\le y\), herstellbaren Seitenlängen und
$$10y\le 11x,$$
also einem Rechteck, das höchstens \(10\%\) von einem Quadrat abweicht. Gesucht ist
$$\sum_{k=2}^{100} M(k).$$
Die Implementierungen kodieren die Herstellbarkeit über die Seitenlängen: Eine positive ganze Zahl ist genau dann zulässig, wenn alle ihre Primfaktoren in \(\{2,3,5,7,11,13,17,19,23\}\) liegen.
Setze
$$P=\{2,3,5,7,11,13,17,19,23\}$$
und definiere die Menge herstellbarer Seiten durch
$$\mathcal{S}=\left\{n\in \mathbb{Z}_{>0}: \text{jeder Primteiler von } n \text{ liegt in } P\right\}.$$
Für eine Fläche \(A\) definieren wir ihre zulässige Vielfachheit als
$$r(A)=\#\left\{(x,y)\in \mathcal{S}^2 : x\le y,\ xy=A,\ 10y\le 11x\right\}.$$
Dann gilt
$$M(k)=\min\{A:r(A)=k\}.$$
Die erlaubten Skalierungen können nur Primfaktoren bis \(23\) in eine Seitenlänge einführen. Umgekehrt ist jede Primzahl aus \(P\) selbst als gültiger Multiplikator verfügbar, daher lassen sich durch wiederholte zulässige Skalierungen alle positiven ganzen Zahlen aufbauen, deren Primteiler nur aus \(P\) stammen.
Damit sind die herstellbaren Seiten genau die \(23\)-glatten positiven ganzen Zahlen. So wird die ursprüngliche Fertigungsbedingung zu einer sauberen zahlentheoretischen Menge \(\mathcal{S}\).
Nachdem die Seiten so geordnet sind, dass \(x\le y\) gilt, entspricht jede Rechteckvariante einer Faktorisierung \(A=xy\) mit
$$x\le y,\qquad 10y\le 11x.$$
Diese Ungleichung zwingt beide Faktoren in die Nähe von \(\sqrt{A}\), und \(x\le y\) entfernt das gespiegelte Doppel \((y,x)\).
Da Produkte \(23\)-glatter Zahlen wieder \(23\)-glatt sind, ist jede zulässige Fläche selbst \(23\)-glatt. Außerdem ist jeder Teiler einer \(23\)-glatten Zahl wieder \(23\)-glatt. Hat man also eine Fläche \(A\) fixiert, dann ist das Zählen herstellbarer Varianten gleichbedeutend mit dem Zählen zulässiger Teilerpaare von \(A\) in der Nähe der Quadratwurzel.
Die Funktion \(r(A)\) zählt, wie viele zulässige nahezu quadratische Faktorisierungen dieselbe Fläche erzeugen. Verschiedene Flächen können dieselbe Vielfachheit besitzen, und \(M(k)\) wählt die kleinste Fläche mit exakt \(k\) Varianten aus.
Damit lautet das Gesamtproblem
$$\sum_{k=2}^{100} M(k).$$
Diese Sicht trennt die Aufgabe in zwei Ebenen: erst alle relevanten Seitenlängen erzeugen, dann die Flächen nach der Anzahl ihrer zulässigen Faktorenpaare gruppieren.
Angenommen, wir erzeugen nur Seitenlängen bis zu einer Grenze \(L\). Bezeichne mit \(r_L(A)\) dieselbe Anzahl wie \(r(A)\), aber nur mit Paaren \(x,y\le L\). Wenn \(L\) wächst, kann die sichtbare Menge von Paaren nur größer werden; \(r_L(A)\) ist also monoton.
Betrachte nun ein beliebiges zulässiges Paar mit Fläche \(A\). Aus \(x\le y\) und \(xy=A\) folgt \(x\le \sqrt{A}\le y\). Zusammen mit \(10y\le 11x\) erhält man
$$y\le \frac{11}{10}x\le \frac{11}{10}\sqrt{A}.$$
Somit ist jedes zulässige Paar zur Fläche \(A\) sicher sichtbar, sobald
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{A}\right\rceil \right\rceil.$$
Wenn alle benötigten Werte \(M(2),\dots,M(100)\) bereits gefunden wurden und diese Ungleichung zusätzlich für
$$A=\max_{2\le k\le 100} M(k)$$
gilt, dann kann kein unsichtbares Paar mehr ein relevantes Minimum verändern.
Die Implementierungen prüfen den Kontrollwert
$$M(3)=889200.$$
Für diese Fläche sind die zulässigen Faktorenpaare
$$ (900,988),\qquad (912,975),\qquad (936,950). $$
Jedes Paar erfüllt \(x\le y\), jedes Produkt ist \(889200\), und jedes Verhältnis \(y/x\) bleibt unter \(1.1\). Außerdem sind alle Seiten \(23\)-glatt:
$$\begin{aligned} 900&=2^2\cdot 3^2\cdot 5^2, & 988&=2^2\cdot 13\cdot 19,\\ 912&=2^4\cdot 3\cdot 19, & 975&=3\cdot 5^2\cdot 13,\\ 936&=2^3\cdot 3^2\cdot 13, & 950&=2\cdot 5^2\cdot 19. \end{aligned}$$
Also ist \(r(889200)=3\), und dies ist die erste Fläche mit Vielfachheit \(3\).
Die C++-, Python- und Java-Implementierungen beginnen mit einer moderaten Seitenobergrenze und erzeugen rekursiv alle \(23\)-glatten Seitenlängen bis zu dieser Grenze. Anschließend wird die Liste sortiert und dedupliziert, sodass jede herstellbare Seitenlänge genau einmal vorkommt.
Danach wird die sortierte Liste mit \(x\le y\) durchsucht. Für jede kürzere Seite \(x\) werden nur längere Seiten bis \(\left\lfloor \frac{11x}{10}\right\rfloor\) betrachtet, weil größere Werte die Beinahe-Quadrat-Bedingung verletzen würden. Jedes zulässige Paar erhöht den Zähler seiner Fläche \(A=xy\). Nach dem vollständigen Durchlauf wird aus der Flächen-Tabelle die kleinste Fläche für jede Vielfachheit \(k\in[2,100]\) entnommen.
Fehlt noch ein Wert \(M(k)\), wird die Seitenobergrenze mit \(10\) multipliziert und der gesamte Vorgang wiederholt. Sobald alle \(M(k)\) von \(2\) bis \(100\) vorhanden sind, prüft die Implementierung noch die Schranke
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{\max_k M(k)}\right\rceil \right\rceil$$
und beweist damit, dass jenseits der aktuellen Grenze kein zulässiges Paar mehr liegt, das irgendein relevantes Minimum verändern könnte. Dann wird die Endsumme ausgegeben.
Sei \(s(L)\) die Anzahl der \(23\)-glatten ganzen Zahlen bis zur endgültigen Grenze \(L\). Das Erzeugen dieser Zahlen ist ausgabeempfindlich; nach dem Sortieren und Entfernen von Duplikaten kostet es \(O(s(L)\log s(L))\) Zeit und \(O(s(L))\) Speicher.
Das Durchmustern der Paare ist im Worst Case \(O(s(L)^2)\), wobei die Bedingung \(10y\le 11x\) nur ein schmales Band nahe der Diagonale zulässt und die praktische Arbeit stark reduziert. Die Flächen-Tabelle benötigt linearen Speicher in der Anzahl der verschiedenen zulässigen Flächen. Da die Grenze geometrisch wächst, dominiert die letzte erfolgreiche Runde die Gesamtlaufzeit.
Her tamsayı \(k\) için \(M(k)\), tam olarak \(k\) üretilebilir varyanta sahip en küçük dikdörtgen alanı olsun. Bir varyant, \(x\le y\) koşulunu sağlayan, iki kenarı da üretilebilir olan ve
$$10y\le 11x$$
eşitsizliğini sağlayan bir \((x,y)\) çarpan çiftidir; yani dikdörtgen kareden en fazla \(10\%\) sapar. İstenen sonuç
$$\sum_{k=2}^{100} M(k).$$
Uygulamalar üretilebilirliği kenar uzunlukları üzerinden kodlar: Bir pozitif tamsayı kenar, ancak ve ancak bütün asal çarpanları \(\{2,3,5,7,11,13,17,19,23\}\) kümesinden geliyorsa geçerlidir.
Şunu tanımlayalım:
$$P=\{2,3,5,7,11,13,17,19,23\}$$
ve üretilebilir kenar kümesini
$$\mathcal{S}=\left\{n\in \mathbb{Z}_{>0}: n \text{ sayısının her asal böleni } P \text{ içindedir}\right\}$$
olarak yazalım. Her alan \(A\) için uygun çokluğu
$$r(A)=\#\left\{(x,y)\in \mathcal{S}^2 : x\le y,\ xy=A,\ 10y\le 11x\right\}$$
şeklinde tanımlayalım. O zaman
$$M(k)=\min\{A:r(A)=k\}.$$
İzin verilen ölçeklendirmeler bir kenara yalnızca \(23\)'ten küçük ya da eşit asal çarpanlar ekleyebilir. Ters yönde, \(P\) içindeki her asal sayı başlı başına geçerli bir çarpandır; dolayısıyla geçerli ölçeklendirmeler tekrarlandığında asal bölenleri yalnızca \(P\)'den gelen her pozitif tamsayı elde edilebilir.
Böylece üretilebilir kenarlar tam olarak \(23\)-smooth pozitif tamsayılardır. Bu gözlem, üretim kuralını temiz bir sayı kuramı kümesi olan \(\mathcal{S}\)'ye dönüştürür.
Kenarları \(x\le y\) olacak şekilde sıraladıktan sonra her varyant,
$$x\le y,\qquad 10y\le 11x$$
koşullarını sağlayan bir \(A=xy\) çarpanlaşmasına karşılık gelir. Bu eşitsizlik iki çarpanı \(\sqrt{A}\) çevresine sıkıştırır; \(x\le y\) koşulu da simetrik kopya olan \((y,x)\)'i ortadan kaldırır.
\(23\)-smooth sayıların çarpımı yine \(23\)-smooth olduğundan, her uygun alanın kendisi de \(23\)-smooth'tur. Ayrıca \(23\)-smooth bir sayının her böleni yine \(23\)-smooth olduğundan, bir \(A\) alanı sabitlendiğinde üretilebilir varyantları saymak ile \(A\)'nın kareköküne yakın uygun bölen çiftlerini saymak aynı şey olur.
\(r(A)\) fonksiyonu, aynı alanı veren uygun kareye-yakın çarpanlaşmaların sayısını tutar. Farklı alanlar aynı çokluğa sahip olabilir; \(M(k)\) ise çokluğu tam olarak \(k\) olan en küçük alanı seçer.
Dolayısıyla tüm problem
$$\sum_{k=2}^{100} M(k)$$
hesabına indirgenir. Böylece görev iki katmana ayrılır: önce ilgili bütün kenar uzunluklarını üretmek, sonra alanları kendilerini üreten uygun çarpan çiftlerinin sayısına göre gruplamak.
Yalnızca \(L\) sınırına kadar olan kenarları ürettiğimizi varsayalım. \(r_L(A)\), \(r(A)\) ile aynı sayımı yapsın ama yalnızca \(x,y\le L\) olan çiftleri saysın. \(L\) büyüdükçe görülebilen çift kümesi sadece genişler; yani \(r_L(A)\) monotondur.
Şimdi alanı \(A\) olan herhangi bir uygun çifti düşünelim. \(x\le y\) ve \(xy=A\) olduğundan \(x\le \sqrt{A}\le y\) olur. Bunu \(10y\le 11x\) ile birleştirince
$$y\le \frac{11}{10}x\le \frac{11}{10}\sqrt{A}$$
elde edilir. O halde alanı \(A\) olan her uygun çift, şu koşul sağlandığında mutlaka görünür olur:
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{A}\right\rceil \right\rceil.$$
Eğer gerekli bütün \(M(2),\dots,M(100)\) değerleri zaten bulunmuşsa ve bu eşitsizlik ayrıca
$$A=\max_{2\le k\le 100} M(k)$$
için de geçerliyse, artık görünmeyen hiçbir çift ilgili minimumlardan birini değiştiremez.
Uygulamalar şu kontrol değerini doğrular:
$$M(3)=889200.$$
Bu alan için uygun çarpan çiftleri şunlardır:
$$ (900,988),\qquad (912,975),\qquad (936,950). $$
Her çift \(x\le y\) koşulunu sağlar, her birinin çarpımı \(889200\)'dür ve her \(y/x\) oranı \(1.1\)'den küçüktür. Ayrıca bütün kenarlar \(23\)-smooth'tur:
$$\begin{aligned} 900&=2^2\cdot 3^2\cdot 5^2, & 988&=2^2\cdot 13\cdot 19,\\ 912&=2^4\cdot 3\cdot 19, & 975&=3\cdot 5^2\cdot 13,\\ 936&=2^3\cdot 3^2\cdot 13, & 950&=2\cdot 5^2\cdot 19. \end{aligned}$$
Dolayısıyla \(r(889200)=3\) olur ve bu, çokluğu \(3\) olan ilk alandır.
C++, Python ve Java uygulamaları önce orta büyüklükte bir kenar sınırı seçer ve bu sınıra kadar bütün \(23\)-smooth kenar uzunluklarını özyinelemeli olarak üretir. Daha sonra liste sıralanır ve tekrarlar atılır; böylece her üretilebilir kenar yalnızca bir kez işlenir.
Sonra sıralı liste \(x\le y\) olacak biçimde taranır. Her kısa kenar \(x\) için yalnızca \(\left\lfloor \frac{11x}{10}\right\rfloor\) değerine kadar olan uzun kenarlar incelenir; çünkü daha büyük değerler kareye-yakın koşulunu bozar. Her uygun çift, alanı \(A=xy\) için sayacı bir artırır. Bütün çiftler tamamlandığında, alan-sayım tablosundan \(k\in[2,100]\) aralığındaki her çokluk için en küçük alan çekilir.
Eğer bazı \(M(k)\) değerleri hâlâ eksikse, kenar sınırı \(10\) ile çarpılır ve süreç tekrar edilir. \(2\) ile \(100\) arasındaki tüm \(M(k)\) değerleri göründüğünde uygulama şu kapsama eşitsizliğini kontrol eder:
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{\max_k M(k)}\right\rceil \right\rceil$$
Bu kontrol, ilgili hiçbir alan için görünmeyen uygun çift kalmadığını kanıtlar. Böylece son toplam döndürülür.
Son sınır \(L\) için \(s(L)\), \(L\)'ye kadar olan \(23\)-smooth tamsayı sayısı olsun. Bu sayıların üretilmesi çıktı-duyarlıdır; sıralama ve tekilleştirme sonrası zaman maliyeti \(O(s(L)\log s(L))\), bellek maliyeti \(O(s(L))\) olur.
Çift taraması en kötü durumda \(O(s(L)^2)\) düzeyindedir; ancak \(10y\le 11x\) kısıtı yalnızca köşegen çevresindeki dar bir bandı açık bıraktığı için pratikte iş yükü çok daha düşüktür. Alan-sayım tablosu, karşılaşılan farklı uygun alan sayısı kadar doğrusal bellek kullanır. Sınır geometrik olarak büyüdüğü için toplam süreyi son başarılı tur belirler.
Para cada entero \(k\), sea \(M(k)\) el área mínima de un rectángulo con exactamente \(k\) variantes fabricables. Una variante es un par de factores admisible \((x,y)\) con \(x\le y\), ambos lados fabricables y
$$10y\le 11x,$$
de modo que el rectángulo está a lo sumo un \(10\%\) alejado de un cuadrado. El valor pedido es
$$\sum_{k=2}^{100} M(k).$$
Las implementaciones codifican la fabricabilidad por medio de las longitudes de los lados: un lado entero positivo es válido exactamente cuando todos sus factores primos pertenecen a \(\{2,3,5,7,11,13,17,19,23\}\).
Sea
$$P=\{2,3,5,7,11,13,17,19,23\}$$
y definamos el conjunto de lados fabricables por
$$\mathcal{S}=\left\{n\in \mathbb{Z}_{>0}: \text{todo divisor primo de } n \text{ pertenece a } P\right\}.$$
Para cualquier área \(A\), definimos su multiplicidad admisible como
$$r(A)=\#\left\{(x,y)\in \mathcal{S}^2 : x\le y,\ xy=A,\ 10y\le 11x\right\}.$$
Entonces
$$M(k)=\min\{A:r(A)=k\}.$$
Los reescalados permitidos solo pueden introducir factores primos de valor a lo sumo \(23\). En sentido inverso, cada primo de \(P\) es por sí mismo un multiplicador permitido, así que repitiendo reescalados válidos se puede construir cualquier entero positivo cuyos divisores primos estén todos en \(P\).
Por tanto, los lados fabricables son exactamente los enteros positivos \(23\)-suaves. Esto transforma la restricción de fabricación en un conjunto puramente aritmético \(\mathcal{S}\).
Una vez ordenados los lados como \(x\le y\), cada variante del rectángulo corresponde a una factorización \(A=xy\) que satisface
$$x\le y,\qquad 10y\le 11x.$$
La desigualdad obliga a que los dos factores queden cerca de \(\sqrt{A}\), y la condición \(x\le y\) elimina el duplicado simétrico \((y,x)\).
Como el producto de números \(23\)-suaves sigue siendo \(23\)-suave, toda área admisible también lo es. Además, todo divisor de un número \(23\)-suave vuelve a ser \(23\)-suave. Así, una vez fijada un área \(A\), contar variantes fabricables equivale a contar los pares de divisores admisibles de \(A\) cercanos a su raíz cuadrada.
La función \(r(A)\) cuenta cuántas factorizaciones admisibles y casi cuadradas producen la misma área. Distintas áreas pueden compartir la misma multiplicidad, y \(M(k)\) selecciona la menor área cuya multiplicidad es exactamente \(k\).
Por eso, el problema completo se reduce a
$$\sum_{k=2}^{100} M(k).$$
Esta reformulación separa el trabajo en dos fases: enumerar todos los lados relevantes y luego agrupar las áreas según el número de pares de factores admisibles que las generan.
Supongamos que solo enumeramos lados hasta un tope \(L\). Sea \(r_L(A)\) el mismo conteo que \(r(A)\), pero restringido a pares con \(x,y\le L\). Cuando \(L\) aumenta, el conjunto de pares visibles solo puede crecer, así que \(r_L(A)\) es monótona.
Ahora tomemos cualquier par admisible de área \(A\). Como \(x\le y\) y \(xy=A\), se tiene \(x\le \sqrt{A}\le y\). Combinando esto con \(10y\le 11x\), obtenemos
$$y\le \frac{11}{10}x\le \frac{11}{10}\sqrt{A}.$$
Por consiguiente, todos los pares admisibles del área \(A\) están garantizados dentro del tope una vez que
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{A}\right\rceil \right\rceil.$$
Si ya se han encontrado todos los valores \(M(2),\dots,M(100)\) y esta desigualdad también vale para
$$A=\max_{2\le k\le 100} M(k),$$
entonces ningún par todavía invisible puede modificar alguno de los mínimos relevantes.
Las implementaciones verifican el control
$$M(3)=889200.$$
Para esa área, los pares de factores admisibles son
$$ (900,988),\qquad (912,975),\qquad (936,950). $$
Cada par satisface \(x\le y\), cada producto es \(889200\), y cada cociente \(y/x\) es menor que \(1.1\). Además, todos los lados son \(23\)-suaves:
$$\begin{aligned} 900&=2^2\cdot 3^2\cdot 5^2, & 988&=2^2\cdot 13\cdot 19,\\ 912&=2^4\cdot 3\cdot 19, & 975&=3\cdot 5^2\cdot 13,\\ 936&=2^3\cdot 3^2\cdot 13, & 950&=2\cdot 5^2\cdot 19. \end{aligned}$$
Por lo tanto, \(r(889200)=3\), y esa es la primera área con multiplicidad \(3\).
Las implementaciones en C++, Python y Java empiezan con un tope moderado para los lados y generan recursivamente todas las longitudes \(23\)-suaves hasta ese tope. Después, la lista se ordena y se eliminan duplicados para procesar cada lado fabricable una sola vez.
A continuación, la lista ordenada se recorre con \(x\le y\). Para cada lado corto \(x\), solo se consideran lados largos hasta \(\left\lfloor \frac{11x}{10}\right\rfloor\), porque cualquier valor mayor violaría la condición de proximidad al cuadrado. Cada par admisible incrementa el contador de su área \(A=xy\). Tras procesar todos los pares, se extrae de la tabla de áreas la menor área para cada multiplicidad \(k\in[2,100]\).
Si todavía falta algún \(M(k)\), el tope de los lados se multiplica por \(10\) y todo el proceso se repite. Cuando ya han aparecido todos los \(M(k)\) entre \(2\) y \(100\), la implementación comprueba además la cota
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{\max_k M(k)}\right\rceil \right\rceil$$
para demostrar que no existe ningún par admisible relevante fuera del tope actual. En ese momento devuelve la suma final.
Sea \(s(L)\) el número de enteros \(23\)-suaves hasta el tope final \(L\). La generación de estos números es sensible al tamaño de la salida; después de ordenar y eliminar duplicados cuesta \(O(s(L)\log s(L))\) tiempo y \(O(s(L))\) memoria.
El barrido de pares es \(O(s(L)^2)\) en el peor caso, aunque la restricción \(10y\le 11x\) deja solo una banda estrecha cerca de la diagonal y reduce mucho el trabajo real. La tabla de conteo de áreas usa memoria lineal en el número de áreas admisibles distintas que aparecen. Como el tope crece geométricamente, la última ronda exitosa domina el tiempo total.
对每个整数 \(k\)，记 \(M(k)\) 为“恰好有 \(k\) 个可制造变体”的最小矩形面积。这里一个变体就是一个满足 \(x\le y\) 的可行因子对 \((x,y)\)，它的两条边都必须可制造，并且满足
$$10y\le 11x,$$
也就是长边最多只比短边大 \(10\%\)。题目要求计算
$$\sum_{k=2}^{100} M(k).$$
这些实现把“可制造”转写成整数条件：一个正整数边长是可制造的，当且仅当它的所有素因子都属于 \(\{2,3,5,7,11,13,17,19,23\}\)。
设
$$P=\{2,3,5,7,11,13,17,19,23\}$$
并定义可制造边长集合
$$\mathcal{S}=\left\{n\in \mathbb{Z}_{>0}: n \text{ 的每个素因子都属于 } P\right\}.$$
对任意面积 \(A\)，定义它的可行重数为
$$r(A)=\#\left\{(x,y)\in \mathcal{S}^2 : x\le y,\ xy=A,\ 10y\le 11x\right\}.$$
于是
$$M(k)=\min\{A:r(A)=k\}.$$
允许的放大操作只能给边长引入不超过 \(23\) 的素因子。反过来，\(P\) 中的每个素数本身就是允许的乘子，因此只要不断应用这些合法放大，就能得到所有素因子都来自 \(P\) 的正整数。
所以，可制造边长恰好就是所有 \(23\)-smooth 正整数。这样一来，原来的制造规则就被完全转化成了一个清晰的数论集合 \(\mathcal{S}\)。
将两条边按 \(x\le y\) 排序后，每一个矩形变体都对应于一个分解 \(A=xy\)，并满足
$$x\le y,\qquad 10y\le 11x.$$
这个不等式说明两条边必须靠近 \(\sqrt{A}\)，而 \(x\le y\) 则去掉了镜像重复的 \((y,x)\)。
因为 \(23\)-smooth 数的乘积仍然是 \(23\)-smooth，所以每个可行面积本身也一定是 \(23\)-smooth。进一步地，一个 \(23\)-smooth 数的所有约数仍然都是 \(23\)-smooth。因此，一旦面积 \(A\) 固定，统计可制造变体就等价于统计 \(A\) 的那些既满足比例约束、又靠近平方根的约数对。
函数 \(r(A)\) 记录的是：面积 \(A\) 可以由多少个可行的“近方形”因子对产生。不同面积可能拥有相同的重数，而 \(M(k)\) 则从这些面积中挑出重数恰好为 \(k\) 的最小者。
因此整个题目可以写成
$$\sum_{k=2}^{100} M(k).$$
这样，问题被拆成两层：先枚举所有相关边长，再把面积按“由多少个可行因子对产生”来归类。
假设我们目前只枚举不超过某个上界 \(L\) 的边长。记 \(r_L(A)\) 为与 \(r(A)\) 相同的计数，但只统计 \(x,y\le L\) 的因子对。显然，随着 \(L\) 变大，可见的因子对只会增加，所以 \(r_L(A)\) 关于 \(L\) 是单调不减的。
现在考虑任意一个可行因子对，它满足 \(xy=A\) 且 \(x\le y\)。于是
$$x\le \sqrt{A}\le y.$$
再结合比例条件 \(10y\le 11x\)，得到
$$y\le \frac{11}{10}x\le \frac{11}{10}\sqrt{A}.$$
这说明：只要
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{A}\right\rceil \right\rceil,$$
面积 \(A\) 的所有可行因子对就一定已经全部出现在枚举范围内。于是，如果 \(M(2),\dots,M(100)\) 都已经找到了，并且这个上界条件还对
$$A=\max_{2\le k\le 100} M(k)$$
成立，那么任何尚未枚举到的因子对都不可能改变这些最小值，搜索就可以安全停止。
实现中使用了如下校验值：
$$M(3)=889200.$$
对这个面积，满足条件的因子对恰好有三组：
$$ (900,988),\qquad (912,975),\qquad (936,950). $$
它们都满足 \(x\le y\)，乘积都等于 \(889200\)，而且每个比值 \(y/x\) 都小于 \(1.1\)。另外，这六个边长全部都是 \(23\)-smooth：
$$\begin{aligned} 900&=2^2\cdot 3^2\cdot 5^2, & 988&=2^2\cdot 13\cdot 19,\\ 912&=2^4\cdot 3\cdot 19, & 975&=3\cdot 5^2\cdot 13,\\ 936&=2^3\cdot 3^2\cdot 13, & 950&=2\cdot 5^2\cdot 19. \end{aligned}$$
因此 \(r(889200)=3\)，而且没有更小的面积也具有同样的重数，这正是实现用来确认逻辑正确性的检查点。
C++、Python 和 Java 实现都会先取一个中等规模的边长上界，然后递归生成不超过该上界的全部 \(23\)-smooth 边长。生成后的列表会排序并去重，使每一个可制造边长只被处理一次。
接着，程序在排序后的列表上扫描所有 \(x\le y\) 的组合。对每个较短边 \(x\)，只需要考虑不超过 \(\left\lfloor \frac{11x}{10}\right\rfloor\) 的较长边，因为更大的 \(y\) 一定违反近方形约束。每找到一个可行因子对，就把对应面积 \(A=xy\) 的计数加一。全部扫描完成后，再从面积计数表中提取出每个重数 \(k\in[2,100]\) 对应的最小面积。
如果某些 \(M(k)\) 还没有出现，就把边长上界乘以 \(10\) 并重新执行。等到 \(2\) 到 \(100\) 的所有 \(M(k)\) 都已经找到后，程序还会检查覆盖条件
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{\max_k M(k)}\right\rceil \right\rceil$$
以证明对所有相关面积而言，不会再有新的可行因子对藏在当前上界之外。此时就可以返回最终总和。
记 \(s(L)\) 为最终上界 \(L\) 以内的 \(23\)-smooth 整数个数。生成这些数的过程是输出敏感的；排序并去重之后，时间复杂度为 \(O(s(L)\log s(L))\)，空间复杂度为 \(O(s(L))\)。
因子对扫描在最坏情况下是 \(O(s(L)^2)\)，不过约束 \(10y\le 11x\) 只保留了靠近对角线的一条很窄的带状区域，所以实际工作量会小得多。面积计数表的空间与遇到的不同可行面积数量成线性关系。由于上界按几何级数增长，总运行时间主要由最后一次成功的枚举主导。
Для каждого целого \(k\) обозначим через \(M(k)\) наименьшую площадь прямоугольника, имеющего ровно \(k\) изготовимых вариантов. Вариант задается допустимой парой множителей \((x,y)\), где \(x\le y\), обе стороны изготовимы и выполняется
$$10y\le 11x,$$
то есть прямоугольник отличается от квадрата не более чем на \(10\%\). Требуется вычислить
$$\sum_{k=2}^{100} M(k).$$
Реализации кодируют изготовимость через длины сторон: положительная целая длина допустима тогда и только тогда, когда все ее простые делители принадлежат множеству \(\{2,3,5,7,11,13,17,19,23\}\).
Положим
$$P=\{2,3,5,7,11,13,17,19,23\}$$
и определим множество изготовимых сторон
$$\mathcal{S}=\left\{n\in \mathbb{Z}_{>0}: \text{каждый простой делитель } n \text{ принадлежит } P\right\}.$$
Для любой площади \(A\) определим ее допустимую кратность как
$$r(A)=\#\left\{(x,y)\in \mathcal{S}^2 : x\le y,\ xy=A,\ 10y\le 11x\right\}.$$
Тогда
$$M(k)=\min\{A:r(A)=k\}.$$
Разрешенные масштабирования могут вносить в длину стороны только простые множители, не превосходящие \(23\). Обратно, каждое простое из множества \(P\) само является допустимым множителем, поэтому повторением корректных масштабирований можно получить любой положительный целый, все простые делители которого лежат в \(P\).
Следовательно, изготовимые стороны совпадают в точности с \(23\)-гладкими положительными числами. Так исходное технологическое условие превращается в чисто арифметическое множество \(\mathcal{S}\).
После упорядочивания сторон по правилу \(x\le y\) каждый вариант прямоугольника соответствует разложению \(A=xy\), удовлетворяющему
$$x\le y,\qquad 10y\le 11x.$$
Это неравенство заставляет оба множителя лежать рядом с \(\sqrt{A}\), а условие \(x\le y\) убирает зеркальный дубликат \((y,x)\).
Поскольку произведение \(23\)-гладких чисел снова является \(23\)-гладким, всякая допустимая площадь тоже \(23\)-гладкая. Кроме того, любой делитель \(23\)-гладкого числа снова \(23\)-гладок. Поэтому после фиксации площади \(A\) подсчет изготовимых вариантов равносилен подсчету допустимых пар делителей числа \(A\), расположенных около его квадратного корня.
Функция \(r(A)\) показывает, сколько допустимых почти квадратных факторизаций дают одну и ту же площадь. Разные площади могут иметь одну и ту же кратность, а \(M(k)\) выбирает наименьшую площадь с кратностью ровно \(k\).
Тем самым вся задача сводится к вычислению
$$\sum_{k=2}^{100} M(k).$$
Такое представление делит работу на два этапа: сначала перечислить все нужные длины сторон, затем сгруппировать площади по числу допустимых пар множителей, которые их образуют.
Предположим, что пока перечисляются только стороны не больше некоторого предела \(L\). Пусть \(r_L(A)\) обозначает тот же подсчет, что и \(r(A)\), но только по парам \(x,y\le L\). При росте \(L\) множество видимых пар может лишь расширяться, так что \(r_L(A)\) монотонна.
Рассмотрим любую допустимую пару площади \(A\). Из условий \(x\le y\) и \(xy=A\) следует \(x\le \sqrt{A}\le y\). Вместе с условием \(10y\le 11x\) это дает
$$y\le \frac{11}{10}x\le \frac{11}{10}\sqrt{A}.$$
Значит, все допустимые пары для площади \(A\) гарантированно попадают под предел \(L\), как только
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{A}\right\rceil \right\rceil.$$
Если все нужные значения \(M(2),\dots,M(100)\) уже найдены и это неравенство дополнительно выполняется для
$$A=\max_{2\le k\le 100} M(k),$$
то никакая еще не видимая пара уже не сможет изменить какой-либо из нужных минимумов.
Реализации проверяют контрольное значение
$$M(3)=889200.$$
Для этой площади допустимыми являются ровно три пары множителей:
$$ (900,988),\qquad (912,975),\qquad (936,950). $$
Каждая пара удовлетворяет \(x\le y\), произведение всегда равно \(889200\), а отношение \(y/x\) меньше \(1.1\). Все стороны при этом \(23\)-гладкие:
$$\begin{aligned} 900&=2^2\cdot 3^2\cdot 5^2, & 988&=2^2\cdot 13\cdot 19,\\ 912&=2^4\cdot 3\cdot 19, & 975&=3\cdot 5^2\cdot 13,\\ 936&=2^3\cdot 3^2\cdot 13, & 950&=2\cdot 5^2\cdot 19. \end{aligned}$$
Следовательно, \(r(889200)=3\), и меньшей площади с такой кратностью нет.
Реализации на C++, Python и Java начинают с умеренного предела на длины сторон и рекурсивно генерируют все \(23\)-гладкие стороны до этого предела. Затем список сортируется и очищается от повторов, чтобы каждая изготовимая длина учитывалась ровно один раз.
После этого упорядоченный список просматривается по парам \(x\le y\). Для каждой короткой стороны \(x\) рассматриваются только длинные стороны до \(\left\lfloor \frac{11x}{10}\right\rfloor\), поскольку большие значения немедленно нарушают условие близости к квадрату. Каждая допустимая пара увеличивает счетчик своей площади \(A=xy\). Когда все пары обработаны, из таблицы площадей извлекается минимальная площадь для каждой кратности \(k\in[2,100]\).
Если некоторые \(M(k)\) еще не появились, предел по сторонам умножается на \(10\), и процесс повторяется. Когда все \(M(k)\) от \(2\) до \(100\) уже найдены, дополнительно проверяется оценка
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{\max_k M(k)}\right\rceil \right\rceil$$
и тем самым доказывается, что за текущим пределом не осталось ни одной допустимой пары, способной изменить нужные минимумы. После этого возвращается итоговая сумма.
Пусть \(s(L)\) обозначает число \(23\)-гладких целых чисел, не превосходящих окончательный предел \(L\). Их генерация чувствительна к размеру вывода; после сортировки и удаления повторов она требует \(O(s(L)\log s(L))\) времени и \(O(s(L))\) памяти.
Просмотр пар в худшем случае занимает \(O(s(L)^2)\), хотя ограничение \(10y\le 11x\) оставляет только узкую полосу около диагонали и на практике сильно уменьшает объем работы. Таблица подсчета площадей использует линейную память по числу различных допустимых площадей. Поскольку предел растет геометрически, суммарное время в основном определяется последним успешным проходом.
لكل عدد صحيح \(k\)، نرمز بـ \(M(k)\) إلى أصغر مساحة مستطيل لها بالضبط \(k\) صور قابلة للتصنيع. والصورة هنا هي زوج عوامل مسموح \((x,y)\) يحقق \(x\le y\)، وتكون كلتا الضلعين قابلتين للتصنيع، كما يحقق
$$10y\le 11x,$$
أي إن المستطيل لا يبتعد عن المربع بأكثر من \(10\%\). والمطلوب هو حساب
$$\sum_{k=2}^{100} M(k).$$
تعتمد التطبيقات معيارًا عدديًا للتصنيع: يكون طول الضلع الصحيح الموجب مقبولًا إذا وفقط إذا كانت جميع عوامله الأولية ضمن المجموعة \(\{2,3,5,7,11,13,17,19,23\}\).
لنضع
$$P=\{2,3,5,7,11,13,17,19,23\}$$
ولنعرّف مجموعة الأضلاع القابلة للتصنيع بأنها
$$\mathcal{S}=\left\{\prod_{p\in P} p^{e_p} : e_p\in \mathbb{Z}_{\ge 0}\right\}.$$
ولكل مساحة \(A\)، نعرّف تعددها المسموح بالصيغة
$$r(A)=\#\left\{(x,y)\in \mathcal{S}^2 : x\le y,\ xy=A,\ 10y\le 11x\right\}.$$
وعندئذٍ
$$M(k)=\min\{A:r(A)=k\}.$$
إن عمليات التكبير المسموح بها لا يمكنها إدخال عوامل أولية أكبر من \(23\) في طول الضلع. وبالعكس، فإن كل عدد أولي في \(P\) هو بذاته مضاعِف مسموح، ولذلك يمكن بواسطة التكرار بناء أي عدد صحيح موجب لا تحتوي عوامله الأولية إلا على عناصر من \(P\).
إذًا فالأضلاع القابلة للتصنيع هي بالضبط الأعداد الصحيحة الموجبة \(23\)-smooth. وبهذا تتحول قاعدة التصنيع الأصلية إلى مجموعة عددية واضحة هي \(\mathcal{S}\).
بعد ترتيب الضلعين بحيث \(x\le y\)، تصبح كل صورة لمستطيل مقابلة لتحليل من الشكل \(A=xy\) يحقق
$$x\le y,\qquad 10y\le 11x.$$
يفرض هذا الشرط أن يكون العاملان قريبين من \(\sqrt{A}\)، كما أن شرط \(x\le y\) يزيل النسخة المتناظرة \((y,x)\).
وبما أن حاصل ضرب عددين \(23\)-smooth يبقى \(23\)-smooth، فإن كل مساحة مسموحة هي نفسها \(23\)-smooth. وكذلك فإن كل قاسم لعدد \(23\)-smooth يبقى من النوع نفسه. لذلك، بعد تثبيت مساحة \(A\)، يصبح عدّ الصور القابلة للتصنيع مكافئًا لعدّ أزواج القواسم المسموح بها لتلك المساحة والقريبة من جذرها التربيعي.
تعطي الدالة \(r(A)\) عدد التحليلات المسموح بها والقريبة من المربع التي تنتج المساحة نفسها. وقد تتشارك مساحات مختلفة في التعدد نفسه، بينما تختار \(M(k)\) أصغر مساحة يكون تعددها مساويًا تمامًا لـ \(k\).
وعليه، تصبح المسألة كلها
$$\sum_{k=2}^{100} M(k).$$
وهذه الصياغة تفصل المهمة إلى مستويين: أولًا تعداد جميع أطوال الأضلاع ذات الصلة، ثم تجميع المساحات بحسب عدد أزواج العوامل المسموح بها التي تولدها.
لنفترض أننا نعدّ فقط الأضلاع التي لا تتجاوز حدًا أعلى \(L\). ولْيكن \(r_L(A)\) هو العدّ نفسه مثل \(r(A)\)، لكن مع تقييد الأزواج إلى \(x,y\le L\). عندما يكبر \(L\)، فإن مجموعة الأزواج المرئية لا يمكن إلا أن تزداد، ولذلك فالدالة \(r_L(A)\) رتيبة.
لنأخذ الآن أي زوج مسموح مساحته \(A\). من الشرطين \(x\le y\) و \(xy=A\) نستنتج أن
$$x\le \sqrt{A}\le y.$$
وبضم هذا إلى الشرط \(10y\le 11x\) نحصل على
$$y\le \frac{11}{10}x\le \frac{11}{10}\sqrt{A}.$$
إذن كل زوج مسموح للمساحة \(A\) يكون مضمون الظهور بمجرد أن يتحقق
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{A}\right\rceil \right\rceil.$$
فإذا كانت جميع القيم \(M(2),\dots,M(100)\) قد وُجدت بالفعل، وكان هذا الشرط صحيحًا أيضًا من أجل
$$A=\max_{2\le k\le 100} M(k),$$
فلن يبقى أي زوج غير مرئي قادر على تغيير أي حد أدنى مهم.
تتحقق التطبيقات من القيمة
$$M(3)=889200.$$
ولهذه المساحة تكون أزواج العوامل المسموح بها هي
$$ (900,988),\qquad (912,975),\qquad (936,950). $$
كل زوج يحقق \(x\le y\)، وكل حاصل ضرب يساوي \(889200\)، وكل نسبة \(y/x\) أصغر من \(1.1\). كما أن جميع هذه الأضلاع من النوع \(23\)-smooth:
$$\begin{aligned} 900&=2^2\cdot 3^2\cdot 5^2, & 988&=2^2\cdot 13\cdot 19,\\ 912&=2^4\cdot 3\cdot 19, & 975&=3\cdot 5^2\cdot 13,\\ 936&=2^3\cdot 3^2\cdot 13, & 950&=2\cdot 5^2\cdot 19. \end{aligned}$$
وعليه فإن \(r(889200)=3\)، وهذه أول مساحة تمتلك هذا التعدد.
تبدأ تطبيقات C++ وPython وJava بحد متوسط للأضلاع، ثم تولّد بطريقة عودية جميع الأطوال \(23\)-smooth التي لا تتجاوز ذلك الحد. بعد ذلك تُرتّب القائمة وتُزال التكرارات، بحيث يُعالَج كل ضلع قابل للتصنيع مرة واحدة فقط.
ثم يُفحَص كل زوج يحقق \(x\le y\) داخل القائمة المرتبة. ولكل ضلع أقصر \(x\)، لا تُدرَس إلا الأضلاع الأطول حتى \(\left\lfloor \frac{11x}{10}\right\rfloor\)، لأن أي قيمة أكبر ستكسر شرط القرب من المربع. وكل زوج مسموح يزيد عدّاد المساحة \(A=xy\) بمقدار واحد. وبعد انتهاء الفحص، تُستخرج من جدول المساحات أصغر مساحة لكل تعدد \(k\in[2,100]\).
إذا بقيت بعض القيم \(M(k)\) مفقودة، يُضرَب حد الأضلاع في \(10\) وتُعاد العملية. وعندما تظهر جميع القيم من \(2\) إلى \(100\)، يطبّق التنفيذ أيضًا شرط التغطية
$$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{\max_k M(k)}\right\rceil \right\rceil$$
ليبرهن أنه لم يعد هناك أي زوج مسموح ذي صلة يقع خارج الحد الحالي. عند هذه النقطة تُعاد النهاية المطلوبة.
لنرمز بـ \(s(L)\) إلى عدد الأعداد الصحيحة \(23\)-smooth التي لا تتجاوز الحد النهائي \(L\). إن توليد هذه الأعداد حساس لحجم الخرج؛ وبعد الفرز وإزالة التكرار تكون الكلفة \(O(s(L)\log s(L))\) زمنًا و \(O(s(L))\) ذاكرة.
أما فحص الأزواج فحده الأسوأ هو \(O(s(L)^2)\)، غير أن القيد \(10y\le 11x\) يترك شريطًا ضيقًا فقط قرب القطر، مما يقلل العبء العملي كثيرًا. ويستخدم جدول عدّ المساحات ذاكرة خطية في عدد المساحات المسموح بها المختلفة التي تظهر. وبما أن حد الأضلاع ينمو هندسيًا، فإن الجولة الناجحة الأخيرة هي التي تهيمن على الزمن الكلي.