People arrive in the order \(1,2,3,\dots\). Each new person is placed on the lowest possible floor, and in the first empty room of that floor, such that the sum with the previous occupant on that floor is a perfect square. If \(P(f,r)\) denotes the occupant of floor \(f\), room \(r\), then the target is
$$S(N)=\sum_{\substack{fr=N\\f,r\ge 1}} P(f,r)$$
for \(N=71328803586048\), with only the last eight digits required. The local solutions all reduce this to a closed formula for \(P(f,r)\) together with a divisor scan.
For a fixed floor \(f\), write \(p_t=P(f,t)\). Once the first square root used on that floor is \(s_f\), the greedy hotel rule forces consecutive room pairs to sum to consecutive squares:
$$p_t+p_{t+1}=(s_f+t-1)^2,\qquad t\ge 1.$$
So room \(1\) and room \(2\) sum to \(s_f^2\), room \(2\) and room \(3\) sum to \((s_f+1)^2\), room \(3\) and room \(4\) sum to \((s_f+2)^2\), and so on. This recurrence is the structural core of the implementation.
The C++, Python, and Java solutions all use two floor-specific constants:
$$A_f:=P(f,1)=\begin{cases}1,& f=1,\\ \left\lfloor\frac{f^2}{2}\right\rfloor,& f\ge 2,\end{cases}$$
$$s_f=\begin{cases}2,& f=1,\\ f,& f\equiv 1 \pmod 2,\ f\ge 3,\\ f+1,& f\equiv 0 \pmod 2.\end{cases}$$
The first few floor starters are \(1,2,4,8,12,18,24,\dots\), exactly matching \(\left\lfloor f^2/2\right\rfloor\). These identities are the nontrivial hotel-specific input to person_in_room. The C++ file does not assume them blindly: it greedily simulates the first 30000 arrivals and verifies that the closed form matches every populated entry \(P(f,r)\) for \(f,r\le 60\).
Given \(A_f\), the second room is forced to be
$$P(f,2)=s_f^2-A_f.$$
Because room numbers increase with arrival order, we need \(P(f,2) > A_f\), equivalently \(s_f^2 > 2A_f\). With \(A_f=\lfloor f^2/2\rfloor\), the smallest valid square root is therefore \(f\) on odd floors and \(f+1\) on even floors, exactly as in the code.
Starting from \(p_1=A_f\), the recurrence gives
$$p_{2k}=(s_f+2k-2)^2-p_{2k-1},$$
$$p_{2k+1}=(s_f+2k-1)^2-p_{2k}.$$
Subtracting terms two steps apart removes the alternating dependency:
$$p_{2k+1}-p_{2k-1}=(s_f+2k-1)^2-(s_f+2k-2)^2=2s_f+4k-3,$$
$$p_{2k+2}-p_{2k}=(s_f+2k)^2-(s_f+2k-1)^2=2s_f+4k-1.$$
So the odd-indexed rooms and even-indexed rooms each follow their own arithmetic-difference pattern. Summing those differences yields the formulas used by every implementation:
$$P(f,2k-1)=A_f+(k-1)(2s_f+2k-3),\qquad k\ge 1,$$
$$P(f,2k)=s_f^2-A_f+(k-1)(2s_f+2k-1),\qquad k\ge 1.$$
For \(f=1\), these collapse to the triangular numbers \(1,3,6,10,\dots\), which matches the simulated first floor exactly.
For \(f=10\), we have \(A_{10}=10^2/2=50\) and \(s_{10}=11\). Since room \(20\) is even, \(k=10\), so
$$P(10,20)=11^2-50+(10-1)(2\cdot 11+2\cdot 10-1)=71+9\cdot 41=440.$$
This is one of the explicit checkpoints in the C++ validator. The same file also checks the sample product \(N=20\):
$$S(20)=P(1,20)+P(2,10)+P(4,5)+P(5,4)+P(10,2)+P(20,1),$$
$$S(20)=210+67+34+26+71+200=608.$$
That equality appears directly in run_checkpoints(), so the mathematical derivation and the implementation agree on both room formulas and the divisor-pair summation.
The C++ solver is the authoritative implementation. It computes \(\lfloor\sqrt{N}\rfloor\) with a corrected integer-square-root routine, loops over every divisor candidate \(d\le \lfloor\sqrt{N}\rfloor\), and whenever \(d\mid N\) it adds \(P(d,N/d)\) and, if \(d\ne N/d\), also \(P(N/d,d)\). This matches the ordered-factor-pair definition of \(S(N)\).
The function person_in_room evaluates the formulas above in \(O(1)\) time using unsigned __int128 so that intermediate values cannot overflow. The Python file is a direct translation of the same logic with Python integers. The Java file deliberately does not duplicate the mathematics; it compiles and runs the C++ solver as a bridge, then parses the final number from the program output.
Before printing the target result, the C++ program validates base cases, the checkpoints \(P(10,20)=440\), \(P(25,75)=4863\), \(P(99,100)=19454\), the sample sum \(S(20)=608\), and a brute-force simulation of the first 30000 arrivals. That validation layer is why the closed form can be trusted as the source of truth for the HTML explanation.
Evaluating a single \(P(f,r)\) is \(O(1)\) time and \(O(1)\) memory. The complete solver, as written in the local source files, tests every integer \(d\) from \(1\) to \(\lfloor\sqrt{N}\rfloor\), so the overall running time is \(O(\sqrt{N})\) and the memory usage is \(O(1)\).
For the actual target,
$$N=71328803586048=2^{27}3^{12},\qquad \tau(N)=(27+1)(12+1)=364.$$
So only \(364\) ordered factor pairs contribute to the sum, even though the implementation reaches them by scanning all candidates up to
$$\left\lfloor\sqrt{N}\right\rfloor=8445638.$$
That is still small enough for an immediate computation in all three language variants.
Die Personen kommen in der Reihenfolge \(1,2,3,\dots\) an. Jede neue Person wird auf die niedrigstmögliche Etage und dort in das erste freie Zimmer gesetzt, so dass die Summe mit dem vorherigen Bewohner derselben Etage eine Quadratzahl ist. Bezeichnet \(P(f,r)\) die Person in Etage \(f\), Zimmer \(r\), dann ist gesucht:
$$S(N)=\sum_{\substack{fr=N\\f,r\ge 1}} P(f,r)$$
für \(N=71328803586048\), wobei nur die letzten acht Ziffern benötigt werden. Die lokalen Lösungen reduzieren das Problem auf eine geschlossene Formel für \(P(f,r)\) und eine Schleife über Teilerkandidaten.
Für eine feste Etage \(f\) schreiben wir \(p_t=P(f,t)\). Sobald die erste auf dieser Etage verwendete Quadratwurzel \(s_f\) feststeht, erzwingt die gierige Hotel-Regel eine Kette aufeinanderfolgender Quadrate:
$$p_t+p_{t+1}=(s_f+t-1)^2,\qquad t\ge 1.$$
Also summieren sich Zimmer \(1\) und \(2\) zu \(s_f^2\), Zimmer \(2\) und \(3\) zu \((s_f+1)^2\), dann folgt \((s_f+2)^2\) usw. Genau diese Struktur ist im Code kodiert.
Die Implementierungen in C++, Python und Java arbeiten mit zwei Konstanten pro Etage:
$$A_f:=P(f,1)=\begin{cases}1,& f=1,\\ \left\lfloor\frac{f^2}{2}\right\rfloor,& f\ge 2,\end{cases}$$
$$s_f=\begin{cases}2,& f=1,\\ f,& f\equiv 1 \pmod 2,\ f\ge 3,\\ f+1,& f\equiv 0 \pmod 2.\end{cases}$$
Die ersten Etagenstarter sind \(1,2,4,8,12,18,24,\dots\) und stimmen exakt mit \(\left\lfloor f^2/2\right\rfloor\) ueberein. Diese Identitaeten sind der nichttriviale hotelspezifische Kern von person_in_room. Die C++-Datei validiert sie zudem durch eine brute-force Simulation der ersten 30000 Ankuenfte und prueft, dass die geschlossene Formel fuer alle belegten Werte \(P(f,r)\) mit \(f,r\le 60\) stimmt.
Ist \(A_f\) bekannt, dann ist das zweite Zimmer automatisch
$$P(f,2)=s_f^2-A_f.$$
Wegen der Ankunftsreihenfolge muss \(P(f,2) > A_f\) gelten, also \(s_f^2 > 2A_f\). Mit \(A_f=\lfloor f^2/2\rfloor\) ist die kleinste moegliche Quadratwurzel auf ungeraden Etagen gleich \(f\), auf geraden Etagen gleich \(f+1\), genau wie im Code.
Ausgehend von \(p_1=A_f\) liefert die Rekurrenz
$$p_{2k}=(s_f+2k-2)^2-p_{2k-1},$$
$$p_{2k+1}=(s_f+2k-1)^2-p_{2k}.$$
Wenn man Terme im Abstand zwei subtrahiert, verschwindet die Alternation:
$$p_{2k+1}-p_{2k-1}=(s_f+2k-1)^2-(s_f+2k-2)^2=2s_f+4k-3,$$
$$p_{2k+2}-p_{2k}=(s_f+2k)^2-(s_f+2k-1)^2=2s_f+4k-1.$$
Damit besitzen die ungeraden und geraden Zimmer jeweils ein eigenes arithmetisches Differenzenmuster. Aufsummieren ergibt exakt die beiden vom Programm verwendeten Zweige:
$$P(f,2k-1)=A_f+(k-1)(2s_f+2k-3),\qquad k\ge 1,$$
$$P(f,2k)=s_f^2-A_f+(k-1)(2s_f+2k-1),\qquad k\ge 1.$$
Fuer \(f=1\) reduziert sich das auf die Dreieckszahlen \(1,3,6,10,\dots\), genau wie in der Simulation.
Fuer \(f=10\) gilt \(A_{10}=10^2/2=50\) und \(s_{10}=11\). Da Zimmer \(20\) gerade ist, ist \(k=10\), also
$$P(10,20)=11^2-50+(10-1)(2\cdot 11+2\cdot 10-1)=71+9\cdot 41=440.$$
Genau dieser Wert wird in der C++-Validierung geprueft. Dieselbe Datei testet auch das Produktbeispiel \(N=20\):
$$S(20)=P(1,20)+P(2,10)+P(4,5)+P(5,4)+P(10,2)+P(20,1),$$
$$S(20)=210+67+34+26+71+200=608.$$
Damit stimmen mathematische Ableitung und Implementierung sowohl bei einzelnen Zimmern als auch bei der Teilerpaarsumme ueberein.
Die C++-Loesung ist die massgebliche Implementierung. Zunaechst wird \(\lfloor\sqrt{N}\rfloor\) mit einer korrigierten Ganzzahl-Wurzelfunktion bestimmt. Dann prueft die Schleife jeden Kandidaten \(d\le \lfloor\sqrt{N}\rfloor\); falls \(d\mid N\), werden \(P(d,N/d)\) und, fuer \(d\ne N/d\), auch \(P(N/d,d)\) addiert. Das entspricht genau der Definition ueber geordnete Faktorpaare.
Die Funktion person_in_room wertet die obigen Formeln in \(O(1)\) aus und benutzt unsigned __int128, damit Zwischenwerte nicht ueberlaufen. Die Python-Datei ist eine direkte Uebersetzung derselben Logik mit beliebig grossen Python-Zahlen. Die Java-Datei implementiert die Mathematik bewusst nicht neu, sondern kompiliert und startet die C++-Loesung als Bridge und liest danach den numerischen Output ein.
Vor dem Endergebnis prueft das C++-Programm Basiscases, die Kontrollwerte \(P(10,20)=440\), \(P(25,75)=4863\), \(P(99,100)=19454\), die Beispielsummme \(S(20)=608\) sowie die brute-force Hotelsimulation. Deshalb ist die geschlossene Formel in den lokalen Quellen belastbar abgesichert.
Eine einzelne Auswertung von \(P(f,r)\) kostet \(O(1)\) Zeit und \(O(1)\) Speicher. Der komplette Solver testet in den lokalen Quelldateien jedoch jeden ganzzahligen Kandidaten \(d\) von \(1\) bis \(\lfloor\sqrt{N}\rfloor\), daher liegt die Gesamtlaufzeit bei \(O(\sqrt{N})\) und der Speicherbedarf bei \(O(1)\).
Fuer das konkrete Ziel gilt
$$N=71328803586048=2^{27}3^{12},\qquad \tau(N)=(27+1)(12+1)=364.$$
Es tragen also nur \(364\) geordnete Faktorpaare wirklich zur Summe bei, obwohl die Implementierung alle Kandidaten bis
$$\left\lfloor\sqrt{N}\right\rfloor=8445638$$
durchlaeuft. Fuer diese Groessenordnung ist das trotzdem problemlos schnell.
Insanlar \(1,2,3,\dots\) sirasiyla geliyor. Her yeni kisi, ayni kattaki bir onceki sakinle toplami tam kare olacak sekilde, mumkun olan en dusuk kata ve o kattaki ilk bos odaya yerlestiriliyor. \(P(f,r)\) ifadesi \(f\). kattaki \(r\). odanin sakini olsun. O zaman hedef
$$S(N)=\sum_{\substack{fr=N\\f,r\ge 1}} P(f,r)$$
toplamini \(N=71328803586048\) icin hesaplayip son sekiz basamagi almaktir. Yerel cozumlerin hepsi bunu \(P(f,r)\) icin kapali bir form ve bir bolen taramasi ile yapar.
Sabit bir \(f\) kati icin \(p_t=P(f,t)\) yazalim. Bu katta kullanilan ilk karekok \(s_f\) oldugunda, acgozlu yerlestirme kurali ardışık oda ciftlerinin ardışık karelere toplandigini verir:
$$p_t+p_{t+1}=(s_f+t-1)^2,\qquad t\ge 1.$$
Yani 1. ve 2. odanin toplami \(s_f^2\), 2. ve 3. odanin toplami \((s_f+1)^2\), sonra \((s_f+2)^2\) seklinde ilerler. Kodun omurgasi tam olarak bu bagintidir.
C++, Python ve Java cozumleri her kat icin iki sabit kullaniyor:
$$A_f:=P(f,1)=\begin{cases}1,& f=1,\\ \left\lfloor\frac{f^2}{2}\right\rfloor,& f\ge 2,\end{cases}$$
$$s_f=\begin{cases}2,& f=1,\\ f,& f\equiv 1 \pmod 2,\ f\ge 3,\\ f+1,& f\equiv 0 \pmod 2.\end{cases}$$
Ilk oda degerleri \(1,2,4,8,12,18,24,\dots\) seklinde baslar ve tam olarak \(\left\lfloor f^2/2\right\rfloor\) ile uyusur. Bunlar person_in_room fonksiyonunun hotelsel ozel kimligidir. C++ dosyasi bunlari dogrudan kabul etmekle yetinmez; ilk 30000 kisiyi brute-force yerlestirir ve dolu olan tum \(P(f,r)\) degerleri icin \(f,r\le 60\) araliginda kapali formu dogrular.
\(A_f\) biliniyorsa ikinci oda zorunlu olarak
$$P(f,2)=s_f^2-A_f$$
olur. Varis sirasindan dolayi \(P(f,2) > A_f\) gerekir; bu da \(s_f^2 > 2A_f\) demektir. \(A_f=\lfloor f^2/2\rfloor\) oldugunda en kucuk uygun karekok tek katlarda \(f\), cift katlarda \(f+1\) olur; kod da ayni parcali tanimi kullanir.
Baslangic \(p_1=A_f\) oldugunda baginti sunu verir:
$$p_{2k}=(s_f+2k-2)^2-p_{2k-1},$$
$$p_{2k+1}=(s_f+2k-1)^2-p_{2k}.$$
Iki adim aralikli terimleri cikartirsak almaasik bagimlilik kaybolur:
$$p_{2k+1}-p_{2k-1}=(s_f+2k-1)^2-(s_f+2k-2)^2=2s_f+4k-3,$$
$$p_{2k+2}-p_{2k}=(s_f+2k)^2-(s_f+2k-1)^2=2s_f+4k-1.$$
Boylece tek numarali odalar ve cift numarali odalar kendi iclerinde aritmetik fark desenleri olusturur. Bu farklar toplaninca implementasyonun kullandigi iki kapali dal elde edilir:
$$P(f,2k-1)=A_f+(k-1)(2s_f+2k-3),\qquad k\ge 1,$$
$$P(f,2k)=s_f^2-A_f+(k-1)(2s_f+2k-1),\qquad k\ge 1.$$
\(f=1\) icin bu formuller \(1,3,6,10,\dots\) ucgensel sayilarina iner ve simule edilen ilk kat ile tam uyumludur.
\(f=10\) icin \(A_{10}=10^2/2=50\) ve \(s_{10}=11\). 20. oda cift oldugu icin \(k=10\):
$$P(10,20)=11^2-50+(10-1)(2\cdot 11+2\cdot 10-1)=71+9\cdot 41=440.$$
Bu, C++ dogrulamasindaki acik kontrol noktalarindan biridir. Ayni dosya \(N=20\) icin toplam ornegini de test eder:
$$S(20)=P(1,20)+P(2,10)+P(4,5)+P(5,4)+P(10,2)+P(20,1),$$
$$S(20)=210+67+34+26+71+200=608.$$
Boylece hem tek oda formulleri hem de bolen-cifti toplami, yerel kaynak dosyalar tarafindan dogrudan desteklenmis olur.
Yetkili uygulama C++ cozumudur. Once duzeltilmis bir tamsayi karekok yordamiyla \(\lfloor\sqrt{N}\rfloor\) hesaplanir. Sonra her \(d\le \lfloor\sqrt{N}\rfloor\) adayi test edilir; eger \(d\mid N\) ise \(P(d,N/d)\) eklenir, \(d\ne N/d\) ise simetrik terim \(P(N/d,d)\) de eklenir. Bu tam olarak sirali carpan ciftleri tanimina karsilik gelir.
person_in_room fonksiyonu yukaridaki formulleri \(O(1)\) zamanda hesaplar ve ara degerlerde tasma olmamasi icin unsigned __int128 kullanir. Python dosyasi ayni mantigin dogrudan cevirisidir. Java dosyasi matematigi yeniden yazmaz; C++ cozumunu derleyip calistiran bir kopru gorevi gorur ve ciktiyi parse eder.
C++ programi hedef sonucu basmadan once temel durumlari, \(P(10,20)=440\), \(P(25,75)=4863\), \(P(99,100)=19454\), \(S(20)=608\) kontrollerini ve ilk 30000 kisiye ait brute-force otel simulasyonunu calistirir. Bu nedenle HTML aciklamasi icin en guvenilir kaynak yerel cozum dosyalaridir.
Tek bir \(P(f,r)\) hesabı \(O(1)\) zaman ve \(O(1)\) bellek gerektirir. Ancak yerel kaynaklardaki tam cozum, \(1\) ile \(\lfloor\sqrt{N}\rfloor\) arasindaki her \(d\) tamsayisini denedigi icin toplam calisma suresi \(O(\sqrt{N})\), bellek kullanimi ise \(O(1)\) olur.
Bu problemde
$$N=71328803586048=2^{27}3^{12},\qquad \tau(N)=(27+1)(12+1)=364.$$
Yani toplama gercekte sadece \(364\) sirali carpan cifti katkida bulunur. Buna ragmen uygulama tum adaylari
$$\left\lfloor\sqrt{N}\right\rfloor=8445638$$
degerine kadar tarar. Bu boyut yine de aninda hesaplanabilecek kadar kucuktur.
Las personas llegan en el orden \(1,2,3,\dots\). Cada nueva persona se coloca en el piso mas bajo posible y en la primera habitacion libre de ese piso, de modo que la suma con el ocupante anterior de ese mismo piso sea un cuadrado perfecto. Si \(P(f,r)\) denota al ocupante del piso \(f\), habitacion \(r\), entonces debemos calcular
$$S(N)=\sum_{\substack{fr=N\\f,r\ge 1}} P(f,r)$$
para \(N=71328803586048\), quedandonos solo con las ultimas ocho cifras. Las soluciones locales convierten el problema en una formula cerrada para \(P(f,r)\) mas un recorrido de divisores.
Para un piso fijo \(f\), escribimos \(p_t=P(f,t)\). Una vez conocido el primer cuadrado usado en ese piso, con raiz \(s_f\), la regla voraz del hotel obliga a que las parejas consecutivas sumen cuadrados consecutivos:
$$p_t+p_{t+1}=(s_f+t-1)^2,\qquad t\ge 1.$$
Es decir, las habitaciones \(1\) y \(2\) suman \(s_f^2\), luego vienen \((s_f+1)^2\), \((s_f+2)^2\), etc. Esa recurrencia es la base exacta de la implementacion.
Las soluciones en C++, Python y Java usan dos constantes por piso:
$$A_f:=P(f,1)=\begin{cases}1,& f=1,\\ \left\lfloor\frac{f^2}{2}\right\rfloor,& f\ge 2,\end{cases}$$
$$s_f=\begin{cases}2,& f=1,\\ f,& f\equiv 1 \pmod 2,\ f\ge 3,\\ f+1,& f\equiv 0 \pmod 2.\end{cases}$$
Los primeros ocupantes de piso son \(1,2,4,8,12,18,24,\dots\), exactamente \(\left\lfloor f^2/2\right\rfloor\). Estas identidades son la parte especificamente matematica que el codigo encapsula en person_in_room. El archivo C++ ademas las valida con una simulacion voraz de los primeros 30000 llegados y comprueba que la formula cerrada coincide con todos los valores ocupados \(P(f,r)\) para \(f,r\le 60\).
Con \(A_f\) fijado, la segunda habitacion queda forzada:
$$P(f,2)=s_f^2-A_f.$$
Como el orden de llegada exige \(P(f,2) > A_f\), necesitamos \(s_f^2 > 2A_f\). Si \(A_f=\lfloor f^2/2\rfloor\), la menor raiz posible es \(f\) en pisos impares y \(f+1\) en pisos pares, justo como en el codigo.
Partiendo de \(p_1=A_f\), la recurrencia da
$$p_{2k}=(s_f+2k-2)^2-p_{2k-1},$$
$$p_{2k+1}=(s_f+2k-1)^2-p_{2k}.$$
Si restamos terminos separados por dos posiciones, desaparece la alternancia:
$$p_{2k+1}-p_{2k-1}=(s_f+2k-1)^2-(s_f+2k-2)^2=2s_f+4k-3,$$
$$p_{2k+2}-p_{2k}=(s_f+2k)^2-(s_f+2k-1)^2=2s_f+4k-1.$$
Por tanto, las habitaciones impares y las pares siguen sus propios patrones de diferencias aritmeticas. Sumando esas diferencias obtenemos exactamente las dos ramas del programa:
$$P(f,2k-1)=A_f+(k-1)(2s_f+2k-3),\qquad k\ge 1,$$
$$P(f,2k)=s_f^2-A_f+(k-1)(2s_f+2k-1),\qquad k\ge 1.$$
Para \(f=1\), estas formulas se reducen a los numeros triangulares \(1,3,6,10,\dots\), tal como muestra la simulacion.
Si \(f=10\), entonces \(A_{10}=10^2/2=50\) y \(s_{10}=11\). Como la habitacion \(20\) es par, \(k=10\), luego
$$P(10,20)=11^2-50+(10-1)(2\cdot 11+2\cdot 10-1)=71+9\cdot 41=440.$$
Ese valor aparece como checkpoint explicito en la validacion de C++. El mismo archivo comprueba tambien el ejemplo de producto \(N=20\):
$$S(20)=P(1,20)+P(2,10)+P(4,5)+P(5,4)+P(10,2)+P(20,1),$$
$$S(20)=210+67+34+26+71+200=608.$$
Asi, la derivacion matematica y la suma sobre pares de divisores quedan verificadas contra la implementacion local.
La solucion en C++ es la implementacion principal. Primero calcula \(\lfloor\sqrt{N}\rfloor\) con una rutina de raiz cuadrada entera corregida. Luego recorre cada candidato \(d\le \lfloor\sqrt{N}\rfloor\); cuando \(d\mid N\), suma \(P(d,N/d)\) y, si \(d\ne N/d\), tambien \(P(N/d,d)\). Eso coincide exactamente con la definicion mediante pares ordenados de factores.
La funcion person_in_room evalua las formulas anteriores en tiempo \(O(1)\) usando unsigned __int128 para evitar overflow intermedio. El archivo Python es una traduccion directa de la misma logica. El archivo Java no vuelve a implementar las matematicas: compila y ejecuta el solver de C++ como puente, y luego extrae el numero final de la salida.
Antes de imprimir el resultado objetivo, el programa en C++ valida casos base, los checkpoints \(P(10,20)=440\), \(P(25,75)=4863\), \(P(99,100)=19454\), la suma \(S(20)=608\) y la simulacion voraz de los primeros 30000 llegados. Por eso esas formulas cerradas son la fuente mas fiable para explicar el metodo.
Evaluar un solo \(P(f,r)\) cuesta \(O(1)\) tiempo y \(O(1)\) memoria. Sin embargo, el solver completo tal como esta escrito en los archivos locales prueba todos los enteros \(d\) desde \(1\) hasta \(\lfloor\sqrt{N}\rfloor\), asi que el coste total es \(O(\sqrt{N})\) en tiempo y \(O(1)\) en memoria.
Para el objetivo real,
$$N=71328803586048=2^{27}3^{12},\qquad \tau(N)=(27+1)(12+1)=364.$$
Solo \(364\) pares ordenados de factores aportan realmente a la suma, aunque la implementacion los encuentre escaneando todos los candidatos hasta
$$\left\lfloor\sqrt{N}\right\rfloor=8445638.$$
Aun asi, ese tamano sigue siendo muy pequeno para una ejecucion inmediata.
住客按 \(1,2,3,\dots\) 的顺序到来。每个新来的人都会被放到“尽可能低的楼层”，并且放进该层“最靠前的空房间”，同时满足他与该层前一个住客的编号和是完全平方数。记 \(P(f,r)\) 为第 \(f\) 层第 \(r\) 个房间的住客编号，则题目要求计算
$$S(N)=\sum_{\substack{fr=N\\f,r\ge 1}} P(f,r)$$
其中 \(N=71328803586048\)，最后只保留后八位。仓库中的本地解法都把问题化成 \(P(f,r)\) 的闭式公式，再配合一次约数扫描。
对固定楼层 \(f\)，记 \(p_t=P(f,t)\)。一旦这一层第一次使用的平方根是 \(s_f\)，贪心放置规则就会强制相邻房间之和依次等于连续平方：
$$p_t+p_{t+1}=(s_f+t-1)^2,\qquad t\ge 1.$$
也就是说，第 1 与第 2 个房间之和是 \(s_f^2\)，接着是 \((s_f+1)^2\)、\((s_f+2)^2\) 等等。这正是实现中最核心的递推结构。
C++、Python、Java 三个本地版本都使用同样的两个楼层常量：
$$A_f:=P(f,1)=\begin{cases}1,& f=1,\\ \left\lfloor\frac{f^2}{2}\right\rfloor,& f\ge 2,\end{cases}$$
$$s_f=\begin{cases}2,& f=1,\\ f,& f\equiv 1 \pmod 2,\ f\ge 3,\\ f+1,& f\equiv 0 \pmod 2.\end{cases}$$
前几个楼层首房间编号是 \(1,2,4,8,12,18,24,\dots\)，恰好等于 \(\left\lfloor f^2/2\right\rfloor\)。这就是 person_in_room 中最关键的酒店特有规律。C++ 文件没有把它当作未经验证的猜想：它先用贪心规则显式模拟前 30000 个住客，再检查所有已填充的 \(P(f,r)\)（其中 \(f,r\le 60\)）是否与闭式结果一致。
一旦 \(A_f\) 已知，第二个房间的编号就被唯一确定为
$$P(f,2)=s_f^2-A_f.$$
由于住客编号必须递增，所以需要 \(P(f,2) > A_f\)，也就是 \(s_f^2 > 2A_f\)。把 \(A_f=\lfloor f^2/2\rfloor\) 代入后，最小可行平方根在奇数层是 \(f\)，在偶数层是 \(f+1\)，这与代码完全一致。
从 \(p_1=A_f\) 出发，递推式可写成
$$p_{2k}=(s_f+2k-2)^2-p_{2k-1},$$
$$p_{2k+1}=(s_f+2k-1)^2-p_{2k}.$$
把相隔两个位置的项相减，就能去掉奇偶交替依赖：
$$p_{2k+1}-p_{2k-1}=(s_f+2k-1)^2-(s_f+2k-2)^2=2s_f+4k-3,$$
$$p_{2k+2}-p_{2k}=(s_f+2k)^2-(s_f+2k-1)^2=2s_f+4k-1.$$
因此，奇数房间序列和偶数房间序列分别拥有自己的等差差分结构。把这些差分求和后，得到实现中直接使用的两条公式：
$$P(f,2k-1)=A_f+(k-1)(2s_f+2k-3),\qquad k\ge 1,$$
$$P(f,2k)=s_f^2-A_f+(k-1)(2s_f+2k-1),\qquad k\ge 1.$$
当 \(f=1\) 时，它们退化为三角数列 \(1,3,6,10,\dots\)，与暴力模拟得到的第一层完全吻合。
以 \(f=10\) 为例，有 \(A_{10}=10^2/2=50\)，\(s_{10}=11\)。因为第 20 个房间是偶数房间，所以 \(k=10\)：
$$P(10,20)=11^2-50+(10-1)(2\cdot 11+2\cdot 10-1)=71+9\cdot 41=440.$$
这正是 C++ 校验函数中的一个显式检查点。同一个文件还验证了样例积 \(N=20\)：
$$S(20)=P(1,20)+P(2,10)+P(4,5)+P(5,4)+P(10,2)+P(20,1),$$
$$S(20)=210+67+34+26+71+200=608.$$
所以无论是单个房间公式，还是最终的约数对求和，仓库里的本地实现都给出了直接而且一致的验证。
C++ 版本是权威实现。它先用修正过的整数平方根函数求出 \(\lfloor\sqrt{N}\rfloor\)，然后枚举每个 \(d\le \lfloor\sqrt{N}\rfloor\)。如果 \(d\mid N\)，就把 \(P(d,N/d)\) 加入答案；若 \(d\ne N/d\)，再把对称项 \(P(N/d,d)\) 也加进去。这与 \(S(N)\) 中“有序因子对”的定义完全一致。
person_in_room 用上面的闭式在 \(O(1)\) 时间内计算 \(P(f,r)\)，并使用 unsigned __int128 防止中间值溢出。Python 文件是同一逻辑的直接翻译。Java 文件并没有重新实现数学部分，而是把 C++ 解法编译成桥接程序并执行，然后解析输出结果。
在输出目标值之前，C++ 程序还会检查基础案例、\(P(10,20)=440\)、\(P(25,75)=4863\)、\(P(99,100)=19454\)、样例和 \(S(20)=608\)，以及前 30000 个住客的暴力酒店模拟。因此这套闭式公式并不是孤立猜测，而是被本地源码充分验证过的结果。
单次计算 \(P(f,r)\) 只需要 \(O(1)\) 时间和 \(O(1)\) 空间。按照本地源码的实际写法，完整求解会测试从 \(1\) 到 \(\lfloor\sqrt{N}\rfloor\) 的每个整数 \(d\)，所以总时间复杂度是 \(O(\sqrt{N})\)，空间复杂度是 \(O(1)\)。
对于本题目标，
$$N=71328803586048=2^{27}3^{12},\qquad \tau(N)=(27+1)(12+1)=364.$$
也就是说，真正参与求和的有序因子对只有 \(364\) 个；只是实现为了简单，仍然顺序扫描到了
$$\left\lfloor\sqrt{N}\right\rfloor=8445638.$$
这个规模依然很小，三种本地实现都可以很快完成计算。
Люди прибывают в порядке \(1,2,3,\dots\). Каждый новый человек заселяется на самый низкий возможный этаж и в первую свободную комнату этого этажа так, чтобы сумма с предыдущим жильцом на том же этаже была точным квадратом. Обозначим через \(P(f,r)\) номер человека на этаже \(f\) в комнате \(r\). Тогда требуется вычислить
$$S(N)=\sum_{\substack{fr=N\\f,r\ge 1}} P(f,r)$$
для \(N=71328803586048\) и оставить только последние восемь цифр. Все локальные решения сводят задачу к замкнутой формуле для \(P(f,r)\) и перебору делителей.
Для фиксированного этажа \(f\) положим \(p_t=P(f,t)\). Как только известен первый квадратный корень \(s_f\), используемый на этом этаже, жадное правило гостиницы заставляет соседние комнаты давать подряд идущие квадраты:
$$p_t+p_{t+1}=(s_f+t-1)^2,\qquad t\ge 1.$$
Значит, комнаты \(1\) и \(2\) дают сумму \(s_f^2\), затем идут \((s_f+1)^2\), \((s_f+2)^2\) и так далее. Именно эта рекуррентная структура лежит в основе реализации.
Локальные реализации на C++, Python и Java используют две константы для каждого этажа:
$$A_f:=P(f,1)=\begin{cases}1,& f=1,\\ \left\lfloor\frac{f^2}{2}\right\rfloor,& f\ge 2,\end{cases}$$
$$s_f=\begin{cases}2,& f=1,\\ f,& f\equiv 1 \pmod 2,\ f\ge 3,\\ f+1,& f\equiv 0 \pmod 2.\end{cases}$$
Первые значения \(P(f,1)\) равны \(1,2,4,8,12,18,24,\dots\), то есть точно совпадают с \(\left\lfloor f^2/2\right\rfloor\). Это и есть нетривиальная гостиничная закономерность, зашитая в person_in_room. В файле C++ она дополнительно проверяется жадной симуляцией первых 30000 прибывших, после чего закрытая формула сверяется со всеми заполненными значениями \(P(f,r)\) при \(f,r\le 60\).
Если \(A_f\) известно, то второй номер на этаже обязан быть равен
$$P(f,2)=s_f^2-A_f.$$
Поскольку номера прибывающих растут, нужно \(P(f,2) > A_f\), то есть \(s_f^2 > 2A_f\). При \(A_f=\lfloor f^2/2\rfloor\) минимально возможный корень оказывается равным \(f\) на нечётных этажах и \(f+1\) на чётных, ровно как в коде.
Начиная с \(p_1=A_f\), рекурсия даёт
$$p_{2k}=(s_f+2k-2)^2-p_{2k-1},$$
$$p_{2k+1}=(s_f+2k-1)^2-p_{2k}.$$
Если вычесть члены, отстоящие на две позиции, чередующаяся зависимость исчезает:
$$p_{2k+1}-p_{2k-1}=(s_f+2k-1)^2-(s_f+2k-2)^2=2s_f+4k-3,$$
$$p_{2k+2}-p_{2k}=(s_f+2k)^2-(s_f+2k-1)^2=2s_f+4k-1.$$
Следовательно, последовательности нечётных и чётных комнат имеют собственные арифметические схемы приращений. Суммируя эти приращения, получаем именно те две ветви, которые использует программа:
$$P(f,2k-1)=A_f+(k-1)(2s_f+2k-3),\qquad k\ge 1,$$
$$P(f,2k)=s_f^2-A_f+(k-1)(2s_f+2k-1),\qquad k\ge 1.$$
Для \(f=1\) формулы переходят в треугольные числа \(1,3,6,10,\dots\), что полностью совпадает с симуляцией первого этажа.
Возьмём \(f=10\). Тогда \(A_{10}=10^2/2=50\), а \(s_{10}=11\). Поскольку комната \(20\) чётная, имеем \(k=10\):
$$P(10,20)=11^2-50+(10-1)(2\cdot 11+2\cdot 10-1)=71+9\cdot 41=440.$$
Это одно из явных контрольных значений в C++-валидаторе. Там же проверяется и пример с произведением \(N=20\):
$$S(20)=P(1,20)+P(2,10)+P(4,5)+P(5,4)+P(10,2)+P(20,1),$$
$$S(20)=210+67+34+26+71+200=608.$$
Значит, и формула для отдельной комнаты, и итоговая сумма по парам делителей подтверждаются локальной реализацией напрямую.
Реализация на C++ является основной. Сначала она вычисляет \(\lfloor\sqrt{N}\rfloor\) при помощи аккуратной функции целочисленного квадратного корня. Затем цикл перебирает все кандидаты \(d\le \lfloor\sqrt{N}\rfloor\); если \(d\mid N\), в сумму добавляется \(P(d,N/d)\), а при \(d\ne N/d\) ещё и симметричный член \(P(N/d,d)\). Это точно соответствует определению через упорядоченные пары множителей.
Функция person_in_room вычисляет приведённые выше формулы за \(O(1)\) и использует тип unsigned __int128, чтобы исключить переполнение промежуточных значений. Файл Python является прямым переводом той же логики. Файл Java не переписывает математику заново: он компилирует и запускает C++-решение как мост и затем разбирает полученный вывод.
Перед печатью ответа программа на C++ проверяет базовые случаи, значения \(P(10,20)=440\), \(P(25,75)=4863\), \(P(99,100)=19454\), пример \(S(20)=608\) и грубую симуляцию первых 30000 прибытий. Поэтому именно локальные исходники дают надёжную основу для математического описания.
Вычисление одного \(P(f,r)\) требует \(O(1)\) времени и \(O(1)\) памяти. Полный решатель, как он написан в локальных файлах, проверяет каждый целый \(d\) от \(1\) до \(\lfloor\sqrt{N}\rfloor\), так что итоговая сложность равна \(O(\sqrt{N})\) по времени и \(O(1)\) по памяти.
Для настоящего значения
$$N=71328803586048=2^{27}3^{12},\qquad \tau(N)=(27+1)(12+1)=364.$$
То есть реально в сумме участвуют только \(364\) упорядоченные пары делителей, хотя реализация находит их последовательным просмотром всех кандидатов до
$$\left\lfloor\sqrt{N}\right\rfloor=8445638.$$
Даже такой прямой перебор остаётся очень быстрым для данного \(N\).
يصل النزلاء بالترتيب \(1,2,3,\dots\). وكل شخص جديد يوضع في اقل طابق ممكن، وفي اول غرفة فارغة في ذلك الطابق، بحيث يكون مجموع رقمه مع رقم الساكن السابق في الطابق نفسه عددا مربعا كاملا. اذا رمزنا بـ \(P(f,r)\) الى الشخص الموجود في الطابق \(f\) والغرفة \(r\)، فالمطلوب هو حساب
$$S(N)=\sum_{\substack{fr=N\\f,r\ge 1}} P(f,r)$$
عندما يكون \(N=71328803586048\)، ثم نأخذ اخر ثماني خانات فقط. جميع الحلول المحلية تختزل المسألة الى صيغة مغلقة لـ \(P(f,r)\) مع مسح للقواسم.
لطابق ثابت \(f\)، لنكتب \(p_t=P(f,t)\). بمجرد معرفة اول جذر تربيعي مستخدم في هذا الطابق، ولنسمه \(s_f\)، فإن قاعدة الاسناد الجشعة تفرض ان مجموع كل غرفتين متجاورتين يعطي مربعات متتالية:
$$p_t+p_{t+1}=(s_f+t-1)^2,\qquad t\ge 1.$$
أي ان الغرفتين \(1\) و\(2\) مجموعهما \(s_f^2\)، ثم الغرفتان التاليتان تعطيان \((s_f+1)^2\)، ثم \((s_f+2)^2\)، وهكذا. هذه هي البنية الاساسية التي يبني عليها الكود.
حلول C++ وPython وJava المحلية تعتمد على ثابتين لكل طابق:
$$A_f:=P(f,1)=\begin{cases}1,& f=1,\\ \left\lfloor\frac{f^2}{2}\right\rfloor,& f\ge 2,\end{cases}$$
$$s_f=\begin{cases}2,& f=1,\\ f,& f\equiv 1 \pmod 2,\ f\ge 3,\\ f+1,& f\equiv 0 \pmod 2.\end{cases}$$
القيم الاولى للغرفة الاولى في الطوابق هي \(1,2,4,8,12,18,24,\dots\)، وهي تساوي بالضبط \(\left\lfloor f^2/2\right\rfloor\). هذه هي الهوية الخاصة بالفندق والتي تختبئ داخل الدالة person_in_room. وملف C++ لا يكتفي بافتراضها، بل يجري محاكاة جشعة لاول 30000 وافد ويتأكد من ان الصيغة المغلقة تطابق جميع القيم المملوءة \(P(f,r)\) لكل \(f,r\le 60\).
بمجرد معرفة \(A_f\)، تصبح الغرفة الثانية محددة حتما:
$$P(f,2)=s_f^2-A_f.$$
وبما ان الارقام تزداد مع ترتيب الوصول، فلا بد من تحقق \(P(f,2) > A_f\)، اي \(s_f^2 > 2A_f\). وعند التعويض بـ \(A_f=\lfloor f^2/2\rfloor\)، يكون اصغر جذر صالح هو \(f\) في الطوابق الفردية و\(f+1\) في الطوابق الزوجية، تماما كما في الكود.
ابتداء من \(p_1=A_f\)، تعطينا العلاقة:
$$p_{2k}=(s_f+2k-2)^2-p_{2k-1},$$
$$p_{2k+1}=(s_f+2k-1)^2-p_{2k}.$$
وعند طرح حدود تفصل بينها خطوتان تختفي المراوحة بين الفردي والزوجي:
$$p_{2k+1}-p_{2k-1}=(s_f+2k-1)^2-(s_f+2k-2)^2=2s_f+4k-3,$$
$$p_{2k+2}-p_{2k}=(s_f+2k)^2-(s_f+2k-1)^2=2s_f+4k-1.$$
وهكذا تصبح الغرف الفردية والغرف الزوجية لكل منهما متتالية فروق حسابية مستقلة. وبجمع هذه الفروق نحصل على الصيغتين المستعملتين حرفيا في التنفيذ:
$$P(f,2k-1)=A_f+(k-1)(2s_f+2k-3),\qquad k\ge 1,$$
$$P(f,2k)=s_f^2-A_f+(k-1)(2s_f+2k-1),\qquad k\ge 1.$$
وعندما \(f=1\) تختزل هذه الصيغ الى الاعداد المثلثية \(1,3,6,10,\dots\)، وهذا يطابق المحاكاة المباشرة للطابق الاول.
خذ مثلا \(f=10\). عندئذ \(A_{10}=10^2/2=50\) و\(s_{10}=11\). وبما ان الغرفة \(20\) زوجية، فلدينا \(k=10\):
$$P(10,20)=11^2-50+(10-1)(2\cdot 11+2\cdot 10-1)=71+9\cdot 41=440.$$
وهذه قيمة مذكورة صراحة في اختبارات C++. والملف نفسه يتحقق ايضا من مثال حاصل الضرب \(N=20\):
$$S(20)=P(1,20)+P(2,10)+P(4,5)+P(5,4)+P(10,2)+P(20,1),$$
$$S(20)=210+67+34+26+71+200=608.$$
وهذا يعني ان الصياغة الرياضية ومجموع ازواج القواسم كلاهما مدعومان مباشرة بما تفعله الملفات المحلية.
تنفيذ C++ هو المرجع الاساسي. فهو يحسب \(\lfloor\sqrt{N}\rfloor\) باستعمال دالة دقيقة للجذر التربيعي الصحيح، ثم يمر على كل \(d\le \lfloor\sqrt{N}\rfloor\). فإذا كان \(d\mid N\) يضيف \(P(d,N/d)\)، واذا كان \(d\ne N/d\) يضيف ايضا الحد المتماثل \(P(N/d,d)\). وهذا يطابق تماما تعريف \(S(N)\) على ازواج العوامل المرتبة.
الدالة person_in_room تقيم الصيغ السابقة في زمن \(O(1)\)، وتستعمل النوع unsigned __int128 حتى لا يحدث تجاوز في القيم الوسيطة. ملف Python هو ترجمة مباشرة للمنطق نفسه. اما ملف Java فلا يعيد كتابة الرياضيات، بل يقوم بتجميع حل C++ وتشغيله كجسر ثم يستخرج العدد النهائي من الخرج.
وقبل طباعة النتيجة الهدف، يتحقق برنامج C++ من الحالات الاساسية، ومن القيم \(P(10,20)=440\) و\(P(25,75)=4863\) و\(P(99,100)=19454\)، ومن المثال \(S(20)=608\)، ومن محاكاة جشعة لاول 30000 شخص. ولهذا فالصيغة المغلقة هنا ليست حدسا غير مفحوص، بل نتيجة موثقة داخل المصدر المحلي نفسه.
حساب قيمة واحدة من \(P(f,r)\) يحتاج زمنا \(O(1)\) وذاكرة \(O(1)\). اما الحل الكامل كما هو مكتوب في الملفات المحلية فيفحص كل عدد صحيح \(d\) من \(1\) حتى \(\lfloor\sqrt{N}\rfloor\)، ولذلك يكون التعقيد الكلي \(O(\sqrt{N})\) زمنيا و\(O(1)\) مكانيا.
في المسألة الحالية لدينا
$$N=71328803586048=2^{27}3^{12},\qquad \tau(N)=(27+1)(12+1)=364.$$
إذن عدد ازواج القواسم المرتبة التي تساهم فعليا في المجموع هو \(364\) فقط، مع ان التنفيذ يصل اليها عن طريق فحص جميع المرشحين حتى
$$\left\lfloor\sqrt{N}\right\rfloor=8445638.$$
ومع ذلك يبقى هذا صغيرا جدا، ولذلك يكون التنفيذ سريعا في جميع النسخ المحلية.