Consider a two-pile impartial game with positive piles \((a,b)\). If we sort the position as
$$m=\min(a,b),\qquad M=\max(a,b),$$
then one legal move chooses an integer \(y\) with \(1\le y\le m\) and replaces the position by the positive pair \((y,M-y)\), reordering if necessary. Equivalently, every move keeps the larger pile's total \(M\) and repartitions it into two positive parts, with one chosen part not exceeding the old smaller pile.
The task is to count all losing positions with
$$1\le a,b\le n,\qquad n=7^{17}.$$
A direct dynamic program over the full \(n\times n\) grid is hopeless, so the solution depends on a closed binary characterization of the losing states.
Write every position in sorted form \((m,M)\) with \(m\le M\). The key theorem is that the answer depends only on the bit-length of the smaller pile and one congruence class of the larger pile.
Let
$$k=\lfloor \log_2 m\rfloor+1,\qquad p=2^k.$$
Then \(m\) lies in the binary layer
$$2^{k-1}\le m\le 2^k-1=p-1.$$
The implementations use the following criterion:
$$\boxed{(m,M)\text{ is losing }\Longleftrightarrow M\equiv p-1\pmod p.}$$
So once the smaller pile is known, the larger pile must end with exactly \(k\) binary \(1\)-bits. The rest of the analysis is a proof of this statement and a count of how often it occurs.
Assume
$$M\equiv p-1\pmod p.$$
Take any legal move and sort the child position as \((u,v)\) with \(u\le v\). Because a move repartitions \(M\), we always have
$$u+v=M,\qquad 1\le u<p.$$
Now let
$$q=2^{\lfloor \log_2 u\rfloor+1}.$$
Since \(u<p\), its bit-length is at most \(k\), so \(q\mid p\). If the child were losing, then the same criterion at the smaller scale would force
$$v\equiv q-1\pmod q.$$
But \(M\equiv p-1\pmod p\) implies \(M\equiv q-1\pmod q\) as well, because \(q\mid p\). Therefore
$$u=M-v\equiv (q-1)-(q-1)\equiv 0\pmod q.$$
This is impossible: by definition of \(q\), the smaller number \(u\) satisfies
$$0<u<q.$$
So no legal move can reach a losing child. Hence every position with \(M\equiv p-1\pmod p\) is itself losing.
Now assume
$$M\not\equiv p-1\pmod p.$$
Define the nonzero residue
$$t=(M+1)\bmod p,\qquad 1\le t\le p-1,$$
and let \(y\) be the lowest power of two dividing \(t\):
$$y=2^{\nu_2(t)}.$$
Because \(t<p=2^k\), this power satisfies
$$y\le 2^{k-1}\le m,$$
so moving to \((y,M-y)\) is legal. Write
$$M+1=cp+t,\qquad t=y(2s+1)$$
for integers \(c\ge 0\) and \(s\ge 0\). Then
$$M-y=cp+t-1-y=cp+2sy+y-1.$$
This is at least \(y\): the only way \(cp+2sy-1\) could be negative is \(c=s=0\), which would give \(M=y-1\), contradicting \(y\le m\le M\). Therefore the child really has smaller pile \(y\).
Also, because \(t/y\) is odd,
$$t\equiv y\pmod{2y},$$
hence
$$M-y\equiv -1\pmod{2y}.$$
The smaller pile of the child is \(y\), whose bit-length corresponds exactly to modulus \(2y\). So the child satisfies the losing criterion. Every position outside the residue class \(p-1\) therefore has a move to a losing state and is winning.
Fix \(k\), so \(p=2^k\). The smaller pile can take any value in
$$2^{k-1}\le m\le \min(n,p-1).$$
The number of available smaller piles in this layer is
$$A_k=\min(n,p-1)-2^{k-1}+1.$$
For each such \(m\), the larger pile must satisfy
$$M\equiv p-1\pmod p,\qquad M\le n.$$
Those values are
$$p-1,\ 2p-1,\ 3p-1,\ \dots,$$
so their count is
$$C_k=\left\lfloor\frac{n+1}{p}\right\rfloor=\left\lfloor\frac{n+1}{2^k}\right\rfloor.$$
Notice that every such \(M\) is at least \(p-1\), while every \(m\) in the same layer is at most \(p-1\). Thus the ordering condition \(m\le M\) holds automatically. The number of losing unordered pairs contributed by layer \(k\) is therefore
$$A_k\,C_k.$$
Let \(U(n)\) be the number of losing unordered pairs \((m,M)\) with \(m\le M\). Summing the layers gives
$$U(n)=\sum_{k\ge 1,\ 2^{k-1}\le n} \left(\min(n,2^k-1)-2^{k-1}+1\right)\left\lfloor\frac{n+1}{2^k}\right\rfloor.$$
The final answer counts ordered pairs \((a,b)\), not just sorted ones. Off-diagonal positions contribute twice, but diagonal positions \((x,x)\) should be counted only once. A diagonal pair is losing exactly when
$$x\equiv 2^k-1\pmod{2^k}$$
with \(x<2^k\), which forces
$$x=2^k-1.$$
So the diagonal losing positions are precisely the Mersenne numbers not exceeding \(n\), and their count is
$$D(n)=\#\{k\ge 1:2^k-1\le n\}=\lfloor \log_2(n+1)\rfloor.$$
Hence the required count of ordered losing positions is
$$\boxed{L(n)=2U(n)-D(n).}$$
For \(n=7\) there are three nonempty layers.
For \(k=1\), we have \(m=1\), so \(A_1=1\), and the valid larger piles are \(1,3,5,7\), hence \(C_1=4\).
For \(k=2\), the smaller pile lies in \(\{2,3\}\), so \(A_2=2\), and the valid larger piles are \(3,7\), hence \(C_2=2\).
For \(k=3\), the smaller pile lies in \(\{4,5,6,7\}\), so \(A_3=4\), and the only valid larger pile is \(7\), hence \(C_3=1\).
Therefore
$$U(7)=1\cdot 4+2\cdot 2+4\cdot 1=12.$$
The diagonal losing positions are \((1,1)\), \((3,3)\), and \((7,7)\), so \(D(7)=3\). Thus
$$L(7)=2\cdot 12-3=21,$$
which matches the small verification used by the implementations.
The C++, Python, and Java implementations all evaluate the same closed formula. They first compute \(n=7^{17}\). Then they iterate over bit-length layers \(k=1,2,\dots\) until \(2^{k-1}>n\). In each layer they compute the interval of possible smaller piles, convert it into \(A_k\), compute the number \(C_k\) of valid larger piles with residue \(2^k-1\), and add the product \(A_kC_k\) to the unordered total.
After that, they count the diagonal corrections \(2^k-1\le n\) and combine everything as \(2U(n)-D(n)\). The C++ implementation additionally builds a small brute-force game table for tiny bounds and checks that the binary criterion reproduces every losing position there; the large input itself is handled purely by the closed formula.
The main computation only iterates over powers of two, so it uses \(O(\log n)\) time and \(O(1)\) extra memory. The optional small validation table in the C++ version is cubic-time in the test bound and quadratic-memory, but it is used only for tiny sanity checks and does not affect the asymptotic cost of solving the actual problem.
Betrachtet wird ein imparteiisches Spiel mit zwei positiven Haufen \((a,b)\). Sortiert man eine Stellung als
$$m=\min(a,b),\qquad M=\max(a,b),$$
dann besteht ein legaler Zug darin, eine Zahl \(y\) mit \(1\le y\le m\) zu wählen und die Stellung durch das positive Paar \((y,M-y)\) zu ersetzen, bei Bedarf wieder sortiert. Anders gesagt: Jeder Zug behält die Gesamtsumme des größeren Haufens \(M\) bei und zerlegt sie neu in zwei positive Teile, wobei einer der Teile den alten kleineren Haufen nicht überschreitet.
Gesucht ist die Anzahl aller Verluststellungen mit
$$1\le a,b\le n,\qquad n=7^{17}.$$
Ein vollständiges DP auf dem gesamten \(n\times n\)-Gitter ist unpraktikabel, daher nutzt die Lösung eine geschlossene binäre Charakterisierung der Verlustzustände.
Wir schreiben jede Stellung in sortierter Form \((m,M)\) mit \(m\le M\). Der entscheidende Satz lautet: Die Antwort hängt nur von der Bitlänge des kleineren Haufens und von genau einer Restklasse des größeren Haufens ab.
Setze
$$k=\lfloor \log_2 m\rfloor+1,\qquad p=2^k.$$
Dann liegt \(m\) in der binären Schicht
$$2^{k-1}\le m\le 2^k-1=p-1.$$
Die Implementierungen verwenden das Kriterium
$$\boxed{(m,M)\text{ ist Verlust }\Longleftrightarrow M\equiv p-1\pmod p.}$$
Sobald also der kleinere Haufen feststeht, muss der größere Haufen in Binärdarstellung genau \(k\) abschließende Einsen besitzen. Der Rest der Herleitung beweist diese Aussage und zählt anschließend ihr Auftreten.
Angenommen,
$$M\equiv p-1\pmod p.$$
Betrachte einen beliebigen legalen Zug und sortiere das Kind als \((u,v)\) mit \(u\le v\). Da ein Zug \(M\) nur neu zerlegt, gilt stets
$$u+v=M,\qquad 1\le u<p.$$
Definiere nun
$$q=2^{\lfloor \log_2 u\rfloor+1}.$$
Wegen \(u<p\) ist die Bitlänge von \(u\) höchstens \(k\), also teilt \(q\) die Zahl \(p\). Wäre das Kind eine Verluststellung, dann müsste auf kleinerer Skala gelten
$$v\equiv q-1\pmod q.$$
Aus \(M\equiv p-1\pmod p\) folgt wegen \(q\mid p\) aber auch
$$M\equiv q-1\pmod q.$$
Somit wäre
$$u=M-v\equiv (q-1)-(q-1)\equiv 0\pmod q,$$
was unmöglich ist, denn nach Definition von \(q\) gilt
$$0<u<q.$$
Kein legaler Zug erreicht also eine Verluststellung. Daher ist jede Stellung mit \(M\equiv p-1\pmod p\) selbst eine Verluststellung.
Nehmen wir jetzt an,
$$M\not\equiv p-1\pmod p.$$
Setze den von Null verschiedenen Rest
$$t=(M+1)\bmod p,\qquad 1\le t\le p-1,$$
und wähle \(y\) als kleinste Zweierpotenz, die \(t\) teilt:
$$y=2^{\nu_2(t)}.$$
Da \(t<p=2^k\), gilt
$$y\le 2^{k-1}\le m,$$
also ist der Zug nach \((y,M-y)\) legal. Schreibe
$$M+1=cp+t,\qquad t=y(2s+1)$$
mit \(c\ge 0\) und \(s\ge 0\). Dann folgt
$$M-y=cp+t-1-y=cp+2sy+y-1.$$
Dieser Ausdruck ist mindestens \(y\): Nur im Fall \(c=s=0\) wäre \(cp+2sy-1\) negativ, aber das ergäbe \(M=y-1\), im Widerspruch zu \(y\le m\le M\). Also ist \(y\) tatsächlich der kleinere Haufen des Kindes.
Weil \(t/y\) ungerade ist, gilt ferner
$$t\equiv y\pmod{2y},$$
also
$$M-y\equiv -1\pmod{2y}.$$
Für einen kleineren Haufen \(y\) ist genau der Modul \(2y\) relevant. Das Kind erfüllt daher das Verlustkriterium. Jede Stellung außerhalb der Restklasse \(p-1\) besitzt also einen Zug zu einer Verluststellung und ist damit Gewinnstellung.
Fixiere \(k\), also \(p=2^k\). Der kleinere Haufen kann jeden Wert aus
$$2^{k-1}\le m\le \min(n,p-1)$$
annehmen. Die Anzahl solcher Werte ist
$$A_k=\min(n,p-1)-2^{k-1}+1.$$
Für jedes dieser \(m\) muss der größere Haufen die Bedingung
$$M\equiv p-1\pmod p,\qquad M\le n$$
erfüllen. Diese Werte sind
$$p-1,\ 2p-1,\ 3p-1,\ \dots,$$
also in Anzahl
$$C_k=\left\lfloor\frac{n+1}{p}\right\rfloor=\left\lfloor\frac{n+1}{2^k}\right\rfloor.$$
Jeder solche Wert \(M\) ist mindestens \(p-1\), während jedes \(m\) dieser Schicht höchstens \(p-1\) ist. Deshalb gilt \(m\le M\) automatisch. Der Beitrag dieser Schicht zu den ungeordneten Verlustpaaren ist somit
$$A_k\,C_k.$$
Sei \(U(n)\) die Anzahl der ungeordneten Verlustpaare \((m,M)\) mit \(m\le M\). Dann
$$U(n)=\sum_{k\ge 1,\ 2^{k-1}\le n} \left(\min(n,2^k-1)-2^{k-1}+1\right)\left\lfloor\frac{n+1}{2^k}\right\rfloor.$$
Gesucht sind jedoch geordnete Paare \((a,b)\). Alle nichtdiagonalen Paare zählen doppelt, diagonale Paare \((x,x)\) dagegen nur einfach. Ein diagonales Paar ist genau dann Verlust, wenn
$$x\equiv 2^k-1\pmod{2^k}$$
und zugleich \(x<2^k\), also notwendig
$$x=2^k-1.$$
Die diagonalen Verluststellungen sind also genau die Mersenne-Zahlen bis \(n\), und ihre Anzahl ist
$$D(n)=\#\{k\ge 1:2^k-1\le n\}=\lfloor \log_2(n+1)\rfloor.$$
Damit lautet die gesuchte Anzahl geordneter Verluststellungen
$$\boxed{L(n)=2U(n)-D(n).}$$
Für \(n=7\) gibt es drei nichtleere Schichten.
Für \(k=1\) ist \(m=1\), also \(A_1=1\), und die zulässigen größeren Haufen sind \(1,3,5,7\), also \(C_1=4\).
Für \(k=2\) liegt der kleinere Haufen in \(\{2,3\}\), also \(A_2=2\), und die zulässigen größeren Haufen sind \(3,7\), also \(C_2=2\).
Für \(k=3\) liegt der kleinere Haufen in \(\{4,5,6,7\}\), also \(A_3=4\), und der einzige zulässige größere Haufen ist \(7\), also \(C_3=1\).
Daher
$$U(7)=1\cdot 4+2\cdot 2+4\cdot 1=12.$$
Diagonal verlieren \((1,1)\), \((3,3)\) und \((7,7)\), also \(D(7)=3\). Folglich
$$L(7)=2\cdot 12-3=21,$$
genau wie in der kleinen Verifikation der Implementierungen.
Die Implementierungen in C++, Python und Java werten alle dieselbe geschlossene Formel aus. Zuerst wird \(n=7^{17}\) berechnet. Danach laufen sie über die Bitlängen-Schichten \(k=1,2,\dots\), bis \(2^{k-1}>n\) gilt. In jeder Schicht bestimmen sie das Intervall möglicher kleinerer Haufen, berechnen daraus \(A_k\), zählen die zulässigen größeren Haufen mit Rest \(2^k-1\) und addieren das Produkt \(A_kC_k\) zur ungeordneten Summe.
Anschließend zählen sie die diagonalen Mersenne-Werte \(2^k-1\le n\) und kombinieren alles zu \(2U(n)-D(n)\). Die C++-Implementierung baut zusätzlich für winzige Grenzen eine vollständige Spieltabelle auf und überprüft, dass das binäre Kriterium dort jede Verluststellung korrekt trifft; die eigentliche große Eingabe wird jedoch ausschließlich mit der geschlossenen Formel gelöst.
Die Hauptrechnung läuft nur über Zweierpotenzen und benötigt daher \(O(\log n)\) Zeit sowie \(O(1)\) zusätzlichen Speicher. Die optionale kleine Validierung in C++ hat kubische Laufzeit in der Testgrenze und quadratischen Speicherbedarf, wird aber nur für winzige Kontrollwerte ausgeführt und beeinflusst die asymptotische Komplexität der eigentlichen Lösung nicht.
Iki pozitif yiginli bir tarafsiz oyun dusunelim. Konumu
$$m=\min(a,b),\qquad M=\max(a,b)$$
seklinde siralarsak, yasal bir hamle \(1\le y\le m\) olacak bicimde bir \(y\) secip konumu \((y,M-y)\) pozitif ciftine donusturmektir; gerekirse tekrar siralanir. Baska bir deyisle her hamle toplam olarak buyuk yigindaki \(M\) degerini korur, fakat onu iki pozitif parcaya yeniden ayirir; bu parcalardan biri eski kucuk yigini asamaz.
Amac,
$$1\le a,b\le n,\qquad n=7^{17}$$
icin tum kaybeden konumlari saymaktir. Tum tablo uzerinde dogrudan dinamik programlama yapmak gercek boyutta imkansiz oldugundan, cozum kaybeden durumlar icin kapali bir ikilik olcut kullanir.
Her konumu \(m\le M\) olacak sekilde \((m,M)\) olarak yazalim. Temel teorem sudur: cevap yalnizca kucuk yigini belirleyen bit uzunluguna ve buyuk yigindaki tek bir kalan sinifina baglidir.
Su tanimlari yapalim:
$$k=\lfloor \log_2 m\rfloor+1,\qquad p=2^k.$$
Buna gore \(m\),
$$2^{k-1}\le m\le 2^k-1=p-1$$
araligindaki ikilik katmanda yer alir. Uygulamalarda kullanilan kriter
$$\boxed{(m,M)\text{ kaybedendir }\Longleftrightarrow M\equiv p-1\pmod p.}$$
Yani kucuk yigin belli olduktan sonra, buyuk yiginda sondaki tam \(k\) bitin hepsi \(1\) olmalidir. Geri kalan kisim bu olcutun neden dogru oldugunu ve nasil sayildigini aciklar.
Simdi
$$M\equiv p-1\pmod p$$
oldugunu varsayalim. Herhangi bir yasal hamleden sonra cocuk konumu \((u,v)\) diye siralayalim; burada \(u\le v\). Hamle \(M\) toplamini yeniden parcaladigi icin
$$u+v=M,\qquad 1\le u<p$$
olur. Simdi
$$q=2^{\lfloor \log_2 u\rfloor+1}$$
olsun. \(u<p\) oldugundan \(u\)'nun bit uzunlugu en fazla \(k\)'dir; dolayisiyla \(q\), \(p\)'yi boler. Eger cocuk konum kaybeden olsaydi, ayni kriter daha kucuk olcekte
$$v\equiv q-1\pmod q$$
demek olurdu. Fakat \(M\equiv p-1\pmod p\) ve \(q\mid p\) oldugu icin ayni anda
$$M\equiv q-1\pmod q$$
da gecerlidir. O halde
$$u=M-v\equiv (q-1)-(q-1)\equiv 0\pmod q$$
cikar. Bu imkansizdir; cunku \(q\) tanim geregi \(u\) icin bir ust ikilik sinirdir ve
$$0<u<q$$
olmalidir. Demek ki hicbir yasal hamle kaybeden bir cocuga gitmez; o halde \(M\equiv p-1\pmod p\) olan her konum kendisi kaybedendir.
Simdi
$$M\not\equiv p-1\pmod p$$
olsun. Sifirdan farkli kalani
$$t=(M+1)\bmod p,\qquad 1\le t\le p-1$$
seklinde tanimlayip \(t\)'yi bolen en kucuk iki kuvvetini secelim:
$$y=2^{\nu_2(t)}.$$
\(t<p=2^k\) oldugu icin
$$y\le 2^{k-1}\le m$$
ve \((y,M-y)\) hamlesi yasaldir. Ayrica
$$M+1=cp+t,\qquad t=y(2s+1)$$
olacak sekilde \(c\ge 0\), \(s\ge 0\) yazabiliriz. Bundan
$$M-y=cp+t-1-y=cp+2sy+y-1$$
elde edilir. Bu ifade en az \(y\)'dir; aksi halde ancak \(c=s=0\) olurdu ve bu da \(M=y-1\) vererek \(y\le m\le M\) ile celisirdi. Dolayisiyla cocugun kucuk yigini gercekten \(y\)'dir.
Ayrica \(t/y\) tek sayi oldugundan
$$t\equiv y\pmod{2y}$$
ve dolayisiyla
$$M-y\equiv -1\pmod{2y}$$
olur. Kucuk yigin \(y\) iken ilgili mod tam olarak \(2y\) oldugundan, bu cocuk konum kaybedendir. Demek ki \(p-1\) kalan sinifinin disindaki her konum kaybeden bir konuma hamle yapabildigi icin kazanandir.
\(k\)'yi sabitleyelim; yani \(p=2^k\). Kucuk yigin
$$2^{k-1}\le m\le \min(n,p-1)$$
araligindaki herhangi bir degeri alabilir. Bu katmandaki olasi kucuk yigin sayisi
$$A_k=\min(n,p-1)-2^{k-1}+1$$
olur. Her boyle \(m\) icin buyuk yiginin
$$M\equiv p-1\pmod p,\qquad M\le n$$
olmasi gerekir. Bu degerler
$$p-1,\ 2p-1,\ 3p-1,\ \dots$$
oldigundan sayilari
$$C_k=\left\lfloor\frac{n+1}{p}\right\rfloor=\left\lfloor\frac{n+1}{2^k}\right\rfloor$$
seklindedir. Her boyle \(M\) en az \(p-1\), ayni katmandaki her \(m\) ise en fazla \(p-1\) oldugu icin \(m\le M\) kosulu otomatik saglanir. Bu katmanin sirasiz kaybeden ciftlere katkisi
$$A_k\,C_k$$
olur.
\(m\le M\) kosullu sirasiz kaybeden cift sayisina \(U(n)\) diyelim. O zaman
$$U(n)=\sum_{k\ge 1,\ 2^{k-1}\le n} \left(\min(n,2^k-1)-2^{k-1}+1\right)\left\lfloor\frac{n+1}{2^k}\right\rfloor.$$
Aranan sey ise sirali \((a,b)\) ciftleridir. Kosegen disindaki her konum iki kez sayilir, fakat kosegendeki \((x,x)\) konumlari yalnizca bir kez sayilmalidir. Bir kosegen konum ancak
$$x\equiv 2^k-1\pmod{2^k}$$
ve \(x<2^k\) ise kaybedendir; bu da zorunlu olarak
$$x=2^k-1$$
demektir. Yani kosegendeki kaybedenler \(n\)'i asmayan Mersenne sayilaridir. Bunlarin sayisi
$$D(n)=\#\{k\ge 1:2^k-1\le n\}=\lfloor \log_2(n+1)\rfloor$$
olur. Sonuc olarak istenen sirali kaybeden konum sayisi
$$\boxed{L(n)=2U(n)-D(n).}$$
\(n=7\) icin uc dolu katman vardir.
\(k=1\) icin yalnizca \(m=1\) vardir; dolayisiyla \(A_1=1\). Uygun buyuk yiginler \(1,3,5,7\) oldugu icin \(C_1=4\).
\(k=2\) icin kucuk yigin \(\{2,3\}\) icindedir; dolayisiyla \(A_2=2\). Uygun buyuk yiginler \(3,7\) oldugu icin \(C_2=2\).
\(k=3\) icin kucuk yigin \(\{4,5,6,7\}\) icindedir; dolayisiyla \(A_3=4\). Uygun buyuk yigin yalnizca \(7\) oldugu icin \(C_3=1\).
Boylece
$$U(7)=1\cdot 4+2\cdot 2+4\cdot 1=12.$$
Kosegende kaybedenler \((1,1)\), \((3,3)\) ve \((7,7)\) oldugundan \(D(7)=3\) bulunur. O halde
$$L(7)=2\cdot 12-3=21,$$
ki bu deger uygulamalardaki kucuk dogrulamayla aynidir.
C++, Python ve Java uygulamalari ayni kapali formulu hesaplar. Once \(n=7^{17}\) bulunur. Daha sonra \(2^{k-1}>n\) olana kadar \(k=1,2,\dots\) katmanlari gezilir. Her katmanda kucuk yigina ait aralik bulunur, bundan \(A_k\) hesaplanir, kalani \(2^k-1\) olan uygun buyuk yiginlar sayilarak \(C_k\) elde edilir ve \(A_kC_k\) carpilip sirasiz toplama eklenir.
Sonra \(2^k-1\le n\) kosulunu saglayan kosegen Mersenne degerleri sayilir ve sonuc \(2U(n)-D(n)\) olarak uretilir. C++ uygulamasi buna ek olarak cok kucuk sinirlar icin tam oyun tablosu kurup ikilik kriterin tum kaybeden durumlari dogru verdigini kontrol eder; buyuk girdi ise tamamen kapali formulle cozulur.
Ana hesap yalnizca iki kuvvetleri uzerinden gectigi icin \(O(\log n)\) zamanda ve \(O(1)\) ek bellekle tamamlanir. C++ tarafindaki istege bagli kucuk dogrulama, test siniri icin kubik zaman ve karesel bellek kullanir; ancak yalnizca cok kucuk denetimler icindir ve asil problemin asimptotik maliyetini degistirmez.
Consideremos un juego imparcial con dos montones positivos \((a,b)\). Si ordenamos la posicion como
$$m=\min(a,b),\qquad M=\max(a,b),$$
entonces un movimiento legal consiste en elegir un entero \(y\) con \(1\le y\le m\) y reemplazar la posicion por el par positivo \((y,M-y)\), reordenando si hace falta. De forma equivalente, cada jugada conserva el total del monton mayor \(M\) y lo vuelve a partir en dos partes positivas, una de las cuales no supera al antiguo monton menor.
Debemos contar todas las posiciones perdedoras con
$$1\le a,b\le n,\qquad n=7^{17}.$$
Un DP completo sobre la cuadricula \(n\times n\) es inviable, asi que la solucion usa una caracterizacion binaria cerrada de los estados perdedores.
Escribimos cada posicion ordenada como \((m,M)\) con \(m\le M\). El hecho central es que la respuesta depende solo de la longitud binaria del monton menor y de una clase de congruencia del monton mayor.
Definimos
$$k=\lfloor \log_2 m\rfloor+1,\qquad p=2^k.$$
Entonces \(m\) pertenece a la capa
$$2^{k-1}\le m\le 2^k-1=p-1.$$
El criterio utilizado por las implementaciones es
$$\boxed{(m,M)\text{ es perdedora }\Longleftrightarrow M\equiv p-1\pmod p.}$$
En otras palabras, una vez fijado el monton menor, el monton mayor debe terminar con exactamente \(k\) unos en binario. El resto del razonamiento demuestra esta afirmacion y despues la cuenta.
Supongamos que
$$M\equiv p-1\pmod p.$$
Tomemos cualquier movimiento legal y ordenemos la posicion hija como \((u,v)\) con \(u\le v\). Como un movimiento solo reparte de nuevo el total \(M\), siempre se cumple
$$u+v=M,\qquad 1\le u<p.$$
Ahora definimos
$$q=2^{\lfloor \log_2 u\rfloor+1}.$$
Como \(u<p\), su longitud binaria es a lo sumo \(k\), de modo que \(q\mid p\). Si la posicion hija fuera perdedora, el mismo criterio en la escala menor obligaria a
$$v\equiv q-1\pmod q.$$
Pero \(M\equiv p-1\pmod p\) implica tambien
$$M\equiv q-1\pmod q,$$
porque \(q\) divide a \(p\). Entonces
$$u=M-v\equiv (q-1)-(q-1)\equiv 0\pmod q,$$
lo cual es imposible, ya que por definicion de \(q\) tenemos
$$0<u<q.$$
Por tanto, ningun movimiento legal puede llegar a una hija perdedora. Toda posicion con \(M\equiv p-1\pmod p\) es realmente perdedora.
Supongamos ahora que
$$M\not\equiv p-1\pmod p.$$
Definimos el residuo no nulo
$$t=(M+1)\bmod p,\qquad 1\le t\le p-1,$$
y sea \(y\) la menor potencia de dos que divide a \(t\):
$$y=2^{\nu_2(t)}.$$
Como \(t<p=2^k\), se cumple
$$y\le 2^{k-1}\le m,$$
asi que el movimiento a \((y,M-y)\) es legal. Escribimos
$$M+1=cp+t,\qquad t=y(2s+1)$$
con \(c\ge 0\) y \(s\ge 0\). Entonces
$$M-y=cp+t-1-y=cp+2sy+y-1.$$
Esta cantidad es al menos \(y\): la unica forma de que \(cp+2sy-1\) fuese negativa seria \(c=s=0\), lo que daria \(M=y-1\) y contradiria \(y\le m\le M\). Por lo tanto, el monton menor de la hija es realmente \(y\).
Ademas, como \(t/y\) es impar, tenemos
$$t\equiv y\pmod{2y},$$
y por consiguiente
$$M-y\equiv -1\pmod{2y}.$$
Para un monton menor igual a \(y\), el modulo relevante es precisamente \(2y\). Asi, la hija satisface el criterio perdedor. Toda posicion fuera de la clase \(p-1\) tiene un movimiento hacia una perdedora y, por tanto, es ganadora.
Fijemos \(k\), es decir, \(p=2^k\). El monton menor puede tomar cualquier valor en
$$2^{k-1}\le m\le \min(n,p-1).$$
El numero de opciones para el monton menor en esa capa es
$$A_k=\min(n,p-1)-2^{k-1}+1.$$
Para cada uno de esos \(m\), el monton mayor debe cumplir
$$M\equiv p-1\pmod p,\qquad M\le n.$$
Esos valores son
$$p-1,\ 2p-1,\ 3p-1,\ \dots,$$
asi que su cantidad es
$$C_k=\left\lfloor\frac{n+1}{p}\right\rfloor=\left\lfloor\frac{n+1}{2^k}\right\rfloor.$$
Todo valor asi de \(M\) es al menos \(p-1\), mientras que todo \(m\) de la capa es a lo sumo \(p-1\). Por ello, la condicion \(m\le M\) se satisface automaticamente. La contribucion de la capa a los pares perdedores no ordenados es entonces
$$A_k\,C_k.$$
Sea \(U(n)\) el numero de pares perdedores no ordenados \((m,M)\) con \(m\le M\). Entonces
$$U(n)=\sum_{k\ge 1,\ 2^{k-1}\le n} \left(\min(n,2^k-1)-2^{k-1}+1\right)\left\lfloor\frac{n+1}{2^k}\right\rfloor.$$
Pero el problema pide pares ordenados \((a,b)\). Los pares fuera de la diagonal cuentan dos veces; los diagonales \((x,x)\), solo una. Un par diagonal es perdedor exactamente cuando
$$x\equiv 2^k-1\pmod{2^k}$$
y ademas \(x<2^k\), lo cual fuerza
$$x=2^k-1.$$
Asi, las perdedoras diagonales son precisamente los numeros de Mersenne no mayores que \(n\), y su numero es
$$D(n)=\#\{k\ge 1:2^k-1\le n\}=\lfloor \log_2(n+1)\rfloor.$$
Por tanto, el total pedido de posiciones perdedoras ordenadas es
$$\boxed{L(n)=2U(n)-D(n).}$$
Para \(n=7\) hay tres capas no vacias.
Con \(k=1\), solo aparece \(m=1\), asi que \(A_1=1\), y los montones mayores validos son \(1,3,5,7\), luego \(C_1=4\).
Con \(k=2\), el monton menor pertenece a \(\{2,3\}\), de modo que \(A_2=2\), y los montones mayores validos son \(3,7\), luego \(C_2=2\).
Con \(k=3\), el monton menor pertenece a \(\{4,5,6,7\}\), de modo que \(A_3=4\), y el unico monton mayor valido es \(7\), luego \(C_3=1\).
Por consiguiente,
$$U(7)=1\cdot 4+2\cdot 2+4\cdot 1=12.$$
Las perdedoras diagonales son \((1,1)\), \((3,3)\) y \((7,7)\), asi que \(D(7)=3\). Entonces
$$L(7)=2\cdot 12-3=21,$$
exactamente el valor pequeno de comprobacion usado por las implementaciones.
Las implementaciones en C++, Python y Java evalian la misma formula cerrada. Primero calculan \(n=7^{17}\). Luego recorren las capas de longitud binaria \(k=1,2,\dots\) hasta que \(2^{k-1}>n\). En cada capa determinan el intervalo permitido del monton menor, obtienen \(A_k\), cuentan los montones mayores con residuo \(2^k-1\) para obtener \(C_k\) y agregan el producto \(A_kC_k\) al total no ordenado.
Despues cuentan las correcciones diagonales \(2^k-1\le n\) y combinan todo como \(2U(n)-D(n)\). La implementacion en C++ ademas construye una tabla completa del juego para cotas muy pequenas y verifica que el criterio binario reproduce todas las posiciones perdedoras alli; la entrada grande se resuelve unicamente con la formula cerrada.
El calculo principal solo itera sobre potencias de dos, asi que requiere \(O(\log n)\) tiempo y \(O(1)\) memoria extra. La validacion opcional a pequena escala en C++ tiene tiempo cubico y memoria cuadratica respecto a la cota de prueba, pero se usa solo para chequeos diminutos y no afecta la complejidad asintotica de la solucion real.
考虑一个由两个正整数石子堆 \((a,b)\) 构成的公平组合博弈。把局面按大小写成
$$m=\min(a,b),\qquad M=\max(a,b),$$
则一次合法操作是选择一个整数 \(y\)，满足 \(1\le y\le m\)，并把当前局面改写为正数对 \((y,M-y)\)，必要时再重新排序。等价地说，每一步都保留原来较大堆的总量 \(M\)，只是把它重新拆成两个正部分，其中一个部分不能超过旧的较小堆。
题目要求统计
$$1\le a,b\le n,\qquad n=7^{17}$$
范围内的全部必败态。若直接在整个 \(n\times n\) 网格上做博弈 DP，规模完全不可接受，因此实现采用了一个严格的二进制闭式判据。
下面始终把局面写成排序后的 \((m,M)\)，其中 \(m\le M\)。关键结论是：局面的输赢只取决于较小堆的二进制位长，以及较大堆在某个二的幂模数下是否落在唯一指定的剩余类中。
令
$$k=\lfloor \log_2 m\rfloor+1,\qquad p=2^k.$$
于是 \(m\) 恰好落在区间
$$2^{k-1}\le m\le 2^k-1=p-1.$$
也就是说，所有较小堆位长相同的局面被放进同一层。实现使用的核心判据是
$$\boxed{(m,M)\text{ 是必败态 }\Longleftrightarrow M\equiv p-1\pmod p.}$$
这意味着：一旦较小堆属于第 \(k\) 层，较大堆必须在二进制表示中以恰好 \(k\) 个连续的 \(1\) 结尾。接下来的几步分别证明这个判据的两个方向，再把它转化成计数公式。
先假设
$$M\equiv p-1\pmod p.$$
任取一个合法后继，并把它重新排序成 \((u,v)\)，其中 \(u\le v\)。由于一次操作本质上只是把总和 \(M\) 重新拆分，所以总有
$$u+v=M,\qquad 1\le u<p.$$
对这个后继的较小部分 \(u\)，定义对应的位长模数
$$q=2^{\lfloor \log_2 u\rfloor+1}.$$
因为 \(u<p\)，所以 \(u\) 的位长不超过 \(k\)，从而 \(q\) 一定整除 \(p\)。如果这个后继本身也是必败态，那么按同样的判据，较大部分 \(v\) 必须满足
$$v\equiv q-1\pmod q.$$
另一方面，由于 \(M\equiv p-1\pmod p\) 且 \(q\mid p\)，可立即推出
$$M\equiv q-1\pmod q.$$
于是
$$u=M-v\equiv (q-1)-(q-1)\equiv 0\pmod q.$$
这不可能成立，因为按 \(q\) 的定义，\(u\) 正好满足
$$0<u<q.$$
也就是说，任何合法后继都不可能再次落入必败态。因此，所有满足 \(M\equiv p-1\pmod p\) 的局面本身必定是必败态。
现在假设
$$M\not\equiv p-1\pmod p.$$
定义非零余数
$$t=(M+1)\bmod p,\qquad 1\le t\le p-1,$$
再令 \(y\) 为整除 \(t\) 的最低二次幂，即
$$y=2^{\nu_2(t)}.$$
因为 \(t<p=2^k\)，所以 \(y\) 最多只能到 \(2^{k-1}\)，从而
$$y\le 2^{k-1}\le m.$$
因此把局面走到 \((y,M-y)\) 一定是合法的。把 \(M+1\) 写成
$$M+1=cp+t,\qquad t=y(2s+1)$$
其中 \(c\ge 0\)、\(s\ge 0\)。那么
$$M-y=cp+t-1-y=cp+2sy+y-1.$$
这个值至少为 \(y\)。因为如果它小于 \(y\)，就只能发生在 \(c=s=0\) 时，那会推出 \(M=y-1\)，与 \(y\le m\le M\) 矛盾。所以后继局面的较小堆确实就是 \(y\)。
又由于 \(t/y\) 是奇数，所以
$$t\equiv y\pmod{2y},$$
于是得到
$$M-y\equiv -1\pmod{2y}.$$
而当较小堆等于 \(y\) 时，判据要求考察的模数恰好就是 \(2y\)。这说明子局面正好落在必败态判据中。于是原局面存在一步走向必败态，因此它必然是必胜态。
固定 \(k\)，即固定 \(p=2^k\)。较小堆 \(m\) 可以取的值是
$$2^{k-1}\le m\le \min(n,p-1).$$
这一层可选的较小堆个数为
$$A_k=\min(n,p-1)-2^{k-1}+1.$$
对于这一层中的每个 \(m\)，较大堆都必须满足
$$M\equiv p-1\pmod p,\qquad M\le n.$$
这些 \(M\) 正是
$$p-1,\ 2p-1,\ 3p-1,\ \dots,$$
因此数量为
$$C_k=\left\lfloor\frac{n+1}{p}\right\rfloor=\left\lfloor\frac{n+1}{2^k}\right\rfloor.$$
这里还有一个很方便的事实：所有满足条件的 \(M\) 都至少等于 \(p-1\)，而该层中的所有 \(m\) 都不超过 \(p-1\)，因此排序条件 \(m\le M\) 自动成立。于是这一层对无序必败态总数的贡献就是
$$A_k\,C_k.$$
记 \(U(n)\) 为满足 \(m\le M\) 的无序必败态个数，则
$$U(n)=\sum_{k\ge 1,\ 2^{k-1}\le n} \left(\min(n,2^k-1)-2^{k-1}+1\right)\left\lfloor\frac{n+1}{2^k}\right\rfloor.$$
但题目要求的是有序对 \((a,b)\)。所有非对角局面在有序意义下会出现两次，而对角局面 \((x,x)\) 只能算一次。一个对角局面成为必败态，当且仅当
$$x\equiv 2^k-1\pmod{2^k}$$
并且 \(x<2^k\)，这就只能是
$$x=2^k-1.$$
所以，对角上的必败态正好对应所有不超过 \(n\) 的 Mersenne 数，其个数为
$$D(n)=\#\{k\ge 1:2^k-1\le n\}=\lfloor \log_2(n+1)\rfloor.$$
最终需要的有序必败态总数因此是
$$\boxed{L(n)=2U(n)-D(n).}$$
当 \(n=7\) 时，一共有三层非空区间。
第 \(1\) 层只有 \(m=1\)，因此 \(A_1=1\)。满足条件的较大堆是 \(1,3,5,7\)，故 \(C_1=4\)。
第 \(2\) 层中 \(m\in\{2,3\}\)，因此 \(A_2=2\)。满足条件的较大堆是 \(3,7\)，故 \(C_2=2\)。
第 \(3\) 层中 \(m\in\{4,5,6,7\}\)，因此 \(A_3=4\)。满足条件的较大堆只有 \(7\)，故 \(C_3=1\)。
于是
$$U(7)=1\cdot 4+2\cdot 2+4\cdot 1=12.$$
对角上的必败态为 \((1,1)\)、\((3,3)\)、\((7,7)\)，所以 \(D(7)=3\)。因此
$$L(7)=2\cdot 12-3=21,$$
这与实现中用于小规模校验的结果完全一致。
C++、Python 和 Java 实现都直接计算同一个闭式公式。它们先得到 \(n=7^{17}\)，然后按位长层 \(k=1,2,\dots\) 依次循环，直到 \(2^{k-1}>n\) 为止。在每一层里，先确定较小堆的取值区间，得到 \(A_k\)；再统计不超过 \(n\) 且满足模条件 \(2^k-1\) 的较大堆个数，得到 \(C_k\)；最后把 \(A_kC_k\) 加入无序总数。
之后，再单独统计所有满足 \(2^k-1\le n\) 的对角 Mersenne 值，并按 \(2U(n)-D(n)\) 合成最终答案。C++ 实现还额外对很小的边界构造完整博弈表，逐一核对闭式判据是否与暴力结果一致；真正的大输入则完全依赖上述数学公式。
主算法只遍历二的幂层，因此时间复杂度为 \(O(\log n)\)，额外空间复杂度为 \(O(1)\)。C++ 中的小规模验证仅用于很小的测试上界，时间是三次级别、空间是二次级别，但那只是辅助校验，不影响求解实际输入时的渐近复杂度。
Рассматривается беспристрастная игра с двумя положительными кучами \((a,b)\). Если упорядочить позицию как
$$m=\min(a,b),\qquad M=\max(a,b),$$
то легальный ход выбирает число \(y\) с условием \(1\le y\le m\) и заменяет позицию на положительную пару \((y,M-y)\), при необходимости снова упорядоченную. Эквивалентно, каждый ход сохраняет сумму большей кучи \(M\) и просто разбивает ее заново на две положительные части, одна из которых не превосходит прежнюю меньшую кучу.
Нужно посчитать все проигрышные позиции при
$$1\le a,b\le n,\qquad n=7^{17}.$$
Полная динамика по всей таблице \(n\times n\) здесь нереальна, поэтому решение опирается на точный двоичный критерий проигрыша.
Далее любую позицию записываем в отсортированном виде \((m,M)\), где \(m\le M\). Главный факт таков: результат определяется только длиной двоичной записи меньшей кучи и одной специальной классой вычетов для большей кучи.
Положим
$$k=\lfloor \log_2 m\rfloor+1,\qquad p=2^k.$$
Тогда \(m\) лежит в слое
$$2^{k-1}\le m\le 2^k-1=p-1.$$
Критерий, который используют реализации, имеет вид
$$\boxed{(m,M)\text{ проигрышна }\Longleftrightarrow M\equiv p-1\pmod p.}$$
Иначе говоря, когда длина двоичной записи меньшей кучи равна \(k\), большая куча должна оканчиваться ровно на \(k\) единиц в двоичной форме. Ниже приводится доказательство этого факта и вывод счетной формулы.
Предположим, что
$$M\equiv p-1\pmod p.$$
Рассмотрим любой допустимый ход и упорядочим дочернюю позицию как \((u,v)\), где \(u\le v\). Так как ход лишь заново разбивает сумму \(M\), всегда выполнено
$$u+v=M,\qquad 1\le u<p.$$
Теперь введем число
$$q=2^{\lfloor \log_2 u\rfloor+1}.$$
Поскольку \(u<p\), его двоичная длина не превосходит \(k\), значит \(q\mid p\). Если бы дочерняя позиция тоже была проигрышной, то на меньшем масштабе должно было бы выполняться
$$v\equiv q-1\pmod q.$$
Но из \(M\equiv p-1\pmod p\) и \(q\mid p\) следует также
$$M\equiv q-1\pmod q.$$
Тогда
$$u=M-v\equiv (q-1)-(q-1)\equiv 0\pmod q,$$
что невозможно, потому что по определению \(q\) число \(u\) удовлетворяет
$$0<u<q.$$
Значит, ни один легальный ход не ведет в проигрышную дочернюю позицию. Следовательно, любая позиция с \(M\equiv p-1\pmod p\) сама является проигрышной.
Теперь предположим, что
$$M\not\equiv p-1\pmod p.$$
Определим ненулевой остаток
$$t=(M+1)\bmod p,\qquad 1\le t\le p-1,$$
и возьмем \(y\) как наименьшую степень двойки, делящую \(t\):
$$y=2^{\nu_2(t)}.$$
Так как \(t<p=2^k\), выполняется
$$y\le 2^{k-1}\le m,$$
поэтому ход в \((y,M-y)\) разрешен. Запишем
$$M+1=cp+t,\qquad t=y(2s+1)$$
для некоторых \(c\ge 0\) и \(s\ge 0\). Тогда
$$M-y=cp+t-1-y=cp+2sy+y-1.$$
Это число не меньше \(y\): если бы \(cp+2sy-1\) было отрицательным, пришлось бы иметь \(c=s=0\), а тогда получилось бы \(M=y-1\), что противоречит \(y\le m\le M\). Следовательно, в дочерней позиции меньшая куча действительно равна \(y\).
Кроме того, поскольку \(t/y\) нечетно, имеем
$$t\equiv y\pmod{2y},$$
и значит
$$M-y\equiv -1\pmod{2y}.$$
Для позиции с меньшей кучей \(y\) релевантный модуль как раз равен \(2y\). Следовательно, дочерняя позиция удовлетворяет проигрышному критерию. Значит, любая позиция вне класса \(p-1\) имеет ход в проигрыш и сама является выигрышной.
Зафиксируем \(k\), то есть \(p=2^k\). Меньшая куча может принимать значения из интервала
$$2^{k-1}\le m\le \min(n,p-1).$$
Число таких значений равно
$$A_k=\min(n,p-1)-2^{k-1}+1.$$
Для каждого такого \(m\) большая куча должна удовлетворять условиям
$$M\equiv p-1\pmod p,\qquad M\le n.$$
Это значения вида
$$p-1,\ 2p-1,\ 3p-1,\ \dots,$$
их количество равно
$$C_k=\left\lfloor\frac{n+1}{p}\right\rfloor=\left\lfloor\frac{n+1}{2^k}\right\rfloor.$$
Любое такое \(M\) не меньше \(p-1\), а каждое \(m\) в данном слое не превосходит \(p-1\), поэтому условие \(m\le M\) выполняется автоматически. Вклад слоя в число неупорядоченных проигрышных пар равен
$$A_k\,C_k.$$
Пусть \(U(n)\) обозначает число неупорядоченных проигрышных пар \((m,M)\) при \(m\le M\). Тогда
$$U(n)=\sum_{k\ge 1,\ 2^{k-1}\le n} \left(\min(n,2^k-1)-2^{k-1}+1\right)\left\lfloor\frac{n+1}{2^k}\right\rfloor.$$
Но в задаче требуются упорядоченные пары \((a,b)\). Все внедиагональные позиции учитываются дважды, а диагональные \((x,x)\) должны учитываться один раз. Диагональная позиция проигрышна тогда и только тогда, когда
$$x\equiv 2^k-1\pmod{2^k}$$
и одновременно \(x<2^k\), а это возможно только при
$$x=2^k-1.$$
Следовательно, диагональные проигрышные позиции - это в точности числа Мерсенна, не превосходящие \(n\), и их число равно
$$D(n)=\#\{k\ge 1:2^k-1\le n\}=\lfloor \log_2(n+1)\rfloor.$$
Искомое число упорядоченных проигрышных позиций равно
$$\boxed{L(n)=2U(n)-D(n).}$$
При \(n=7\) существуют три непустых слоя.
Для \(k=1\) возможен только \(m=1\), поэтому \(A_1=1\). Подходящие большие кучи: \(1,3,5,7\), значит \(C_1=4\).
Для \(k=2\) меньшая куча принадлежит множеству \(\{2,3\}\), поэтому \(A_2=2\). Подходящие большие кучи: \(3,7\), значит \(C_2=2\).
Для \(k=3\) меньшая куча лежит в \(\{4,5,6,7\}\), поэтому \(A_3=4\). Подходящая большая куча только одна: \(7\), значит \(C_3=1\).
Следовательно,
$$U(7)=1\cdot 4+2\cdot 2+4\cdot 1=12.$$
Диагональные проигрыши - это \((1,1)\), \((3,3)\) и \((7,7)\), так что \(D(7)=3\). Получаем
$$L(7)=2\cdot 12-3=21,$$
и это совпадает с малой проверкой, используемой в реализациях.
Реализации на C++, Python и Java вычисляют одну и ту же закрытую формулу. Сначала они получают \(n=7^{17}\). Затем перебирают двоичные слои \(k=1,2,\dots\) до тех пор, пока \(2^{k-1}>n\). В каждом слое определяется допустимый интервал для меньшей кучи, из него строится \(A_k\), затем подсчитывается количество больших куч с остатком \(2^k-1\), то есть \(C_k\), и в неупорядоченную сумму добавляется произведение \(A_kC_k\).
После этого отдельно считается диагональная поправка \(2^k-1\le n\), и итог собирается по формуле \(2U(n)-D(n)\). В C++-версии дополнительно строится маленькая полная таблица игры для совсем небольших границ и проверяется, что двоичный критерий совпадает с полным перебором; большое значение \(n\) считается уже только по закрытой формуле.
Основной алгоритм проходит только по степеням двойки, поэтому работает за \(O(\log n)\) времени и требует \(O(1)\) дополнительной памяти. Необязательная малая проверка в C++ имеет кубическую трудоемкость по тестовой границе и квадратичную память, но применяется лишь к очень маленьким контрольным значениям и не влияет на асимптотику реального решения.
لدينا لعبة غير متحيزة بكومتين موجبتين \((a,b)\). إذا رتبنا الوضع على الصورة
$$m=\min(a,b),\qquad M=\max(a,b),$$
فإن الحركة القانونية تختار عددا صحيحا \(y\) بحيث \(1\le y\le m\)، ثم تستبدل الوضع بالزوج الموجب \((y,M-y)\) مع إعادة الترتيب عند الحاجة. وبصياغة مكافئة: كل نقلة تحفظ مجموع الكومة الاكبر \(M\)، ثم تعيد تقسيمه إلى جزأين موجبين، على أن يكون أحد الجزأين غير متجاوز للكومة الاصغر القديمة.
المطلوب هو عد جميع حالات الخسارة عندما
$$1\le a,b\le n,\qquad n=7^{17}.$$
البرمجة الديناميكية المباشرة على شبكة \(n\times n\) مستحيلة عمليا عند هذا الحجم، لذلك يعتمد الحل على معيار ثنائي مغلق يميز حالات الخسارة بدقة.
سنكتب كل وضع بعد الترتيب على هيئة \((m,M)\) حيث \(m\le M\). الفكرة الحاسمة هي أن الربح والخسارة لا يعتمدان على كل تفاصيل الوضع، بل على طول التمثيل الثنائي للكومة الاصغر وعلى فئة توافقية وحيدة للكومة الاكبر.
نضع
$$k=\lfloor \log_2 m\rfloor+1,\qquad p=2^k.$$
عندئذ يقع \(m\) في الطبقة
$$2^{k-1}\le m\le 2^k-1=p-1.$$
المعيار الذي تستعمله التطبيقات هو أن الوضع \((m,M)\) يكون خاسرا إذا وفقط إذا
$$M\equiv p-1\pmod p.$$
هذا يعني أنه إذا كانت الكومة الاصغر ذات طول ثنائي يساوي \(k\)، فلا بد أن تنتهي الكومة الاكبر في الكتابة الثنائية بعدد مقداره \(k\) من الواحدات المتتالية. وما بقي هو تبرير هذا المعيار ثم تحويله إلى صيغة عد.
افترض أن
$$M\equiv p-1\pmod p.$$
خذ أي حركة قانونية، ثم رتب الوضع الناتج في صورة \((u,v)\) حيث \(u\le v\). لأن الحركة لا تفعل إلا إعادة تقسيم المجموع \(M\)، فلدينا دائما
$$u+v=M,\qquad 1\le u<p.$$
الآن عرف
$$q=2^{\lfloor \log_2 u\rfloor+1}.$$
وبما أن \(u<p\)، فإن طول \(u\) الثنائي لا يزيد على \(k\)، ومن ثم \(q\) يقسم \(p\). لو كانت الحالة الابنة خاسرة أيضا، لوجب بحسب المعيار نفسه على المستوى الاصغر أن يتحقق
$$v\equiv q-1\pmod q.$$
لكن من \(M\equiv p-1\pmod p\) ومع \(q\mid p\) نحصل كذلك على
$$M\equiv q-1\pmod q.$$
إذن
$$u=M-v\equiv (q-1)-(q-1)\equiv 0\pmod q,$$
وهذا مستحيل، لأن تعريف \(q\) يفرض
$$0<u<q.$$
وعليه فلا توجد أي نقلة قانونية تصل إلى حالة خاسرة أخرى. لذلك فإن كل وضع يحقق \(M\equiv p-1\pmod p\) هو بنفسه حالة خسارة.
لنفرض الآن أن
$$M\not\equiv p-1\pmod p.$$
عرّف الباقي غير الصفري
$$t=(M+1)\bmod p,\qquad 1\le t\le p-1,$$
ولتكن \(y\) اصغر قوة للعدد \(2\) تقسم \(t\):
$$y=2^{\nu_2(t)}.$$
وبما أن \(t<p=2^k\)، فإن
$$y\le 2^{k-1}\le m,$$
ومن ثم تكون النقلة إلى \((y,M-y)\) قانونية. اكتب
$$M+1=cp+t,\qquad t=y(2s+1)$$
حيث \(c\ge 0\) و\(s\ge 0\). عندئذ
$$M-y=cp+t-1-y=cp+2sy+y-1.$$
وهذا المقدار لا يقل عن \(y\). فالاحتمال الوحيد لكي يصبح \(cp+2sy-1\) سالبا هو \(c=s=0\)، وعندها نحصل على \(M=y-1\)، وهذا يناقض \(y\le m\le M\). إذن الكومة الاصغر في الحالة الابنة هي فعلا \(y\).
ولأن \(t/y\) عدد فردي، فلدينا
$$t\equiv y\pmod{2y},$$
وبالتالي
$$M-y\equiv -1\pmod{2y}.$$
وعندما تكون الكومة الاصغر مساوية لـ \(y\)، فإن المعيار المناسب يستعمل بالضبط modulo \(2y\). وهذا يعني أن الحالة الابنة خاسرة. إذن كل وضع لا يقع في الفئة \(p-1\) يملك نقلة إلى وضع خاسر، ولذلك يكون رابحا.
ثبت \(k\)، أي ثبت \(p=2^k\). يمكن للكومة الاصغر أن تأخذ أي قيمة في المجال
$$2^{k-1}\le m\le \min(n,p-1).$$
ومن ثم يكون عدد القيم الممكنة هو
$$A_k=\min(n,p-1)-2^{k-1}+1.$$
وبالنسبة إلى كل \(m\) من هذه الطبقة، يجب أن تحقق الكومة الاكبر
$$M\equiv p-1\pmod p,\qquad M\le n.$$
وهذه القيم هي
$$p-1,\ 2p-1,\ 3p-1,\ \dots,$$
ولذلك يكون عددها
$$C_k=\left\lfloor\frac{n+1}{p}\right\rfloor=\left\lfloor\frac{n+1}{2^k}\right\rfloor.$$
لاحظ أن كل قيمة من هذا النوع لا تقل عن \(p-1\)، بينما كل \(m\) في الطبقة نفسها لا يزيد على \(p-1\). لذلك فإن الشرط \(m\le M\) متحقق آليا. وهكذا تكون مساهمة هذه الطبقة في عدد حالات الخسارة غير المرتبة هي
$$A_k\,C_k.$$
ليكن \(U(n)\) عدد ازواج الخسارة غير المرتبة \((m,M)\) مع \(m\le M\). عندئذ
$$U(n)=\sum_{k\ge 1,\ 2^{k-1}\le n} \left(\min(n,2^k-1)-2^{k-1}+1\right)\left\lfloor\frac{n+1}{2^k}\right\rfloor.$$
لكن المطلوب في المسألة هو عدد الازواج المرتبة \((a,b)\). الازواج غير القطرية تُحسب مرتين، أما الازواج القطرية \((x,x)\) فيجب أن تُحسب مرة واحدة فقط. ويكون الزوج القطري خاسرا إذا وفقط إذا
$$x\equiv 2^k-1\pmod{2^k}$$
ومع \(x<2^k\)، وهذا يفرض مباشرة
$$x=2^k-1.$$
إذن حالات الخسارة على القطر هي بالضبط اعداد ميرسين التي لا تتجاوز \(n\)، وعددها
$$D(n)=\#\{k\ge 1:2^k-1\le n\}=\lfloor \log_2(n+1)\rfloor.$$
ومن ثم يكون عدد حالات الخسارة المرتبة المطلوبة
$$\boxed{L(n)=2U(n)-D(n).}$$
عندما \(n=7\) توجد ثلاث طبقات غير فارغة.
في الطبقة \(k=1\) لا يوجد إلا \(m=1\)، ولذلك \(A_1=1\). والقيم المسموح بها للكومة الاكبر هي \(1,3,5,7\)، ومن ثم \(C_1=4\).
في الطبقة \(k=2\) يكون \(m\in\{2,3\}\)، ولذلك \(A_2=2\). والقيم المسموح بها للكومة الاكبر هي \(3,7\)، ومن ثم \(C_2=2\).
في الطبقة \(k=3\) يكون \(m\in\{4,5,6,7\}\)، ولذلك \(A_3=4\). والقيمة الوحيدة المناسبة للكومة الاكبر هي \(7\)، ومن ثم \(C_3=1\).
إذن
$$U(7)=1\cdot 4+2\cdot 2+4\cdot 1=12.$$
أما الحالات القطرية الخاسرة فهي \((1,1)\) و\((3,3)\) و\((7,7)\)، وبالتالي \(D(7)=3\). فنحصل على
$$L(7)=2\cdot 12-3=21,$$
وهو نفس المقدار الصغير الذي تستعمله التطبيقات للتحقق.
تقوم تطبيقات C++ وPython وJava جميعا بحساب الصيغة المغلقة نفسها. تبدأ بحساب \(n=7^{17}\)، ثم تدور على طبقات الاطوال الثنائية \(k=1,2,\dots\) حتى يصبح \(2^{k-1}>n\). في كل طبقة تحدد مجال الكومة الاصغر للحصول على \(A_k\)، ثم تعد القيم الممكنة للكومة الاكبر ذات الباقي \(2^k-1\) للحصول على \(C_k\)، ثم تضيف حاصل الضرب \(A_kC_k\) إلى المجموع غير المرتب.
بعد ذلك تعد تصحيح القطر \(2^k-1\le n\)، ثم تجمع النتيجة النهائية بصيغة \(2U(n)-D(n)\). وتضيف نسخة C++ تحققا صغيرا ببناء جدول اللعبة كاملا عند حدود صغيرة جدا، ثم تقارن هذه النتائج مع المعيار الثنائي؛ أما الادخال الكبير الفعلي فيُحل بالكامل بواسطة الصيغة الرياضية فقط.
الخوارزمية الاساسية تمر فقط على قوى العدد \(2\)، ولذلك تعمل في زمن \(O(\log n)\) وبذاكرة اضافية \(O(1)\). اما التحقق الصغير الاختياري في نسخة C++ فزمنه تكعيبي بالنسبة إلى حد الاختبار وذاكرته تربيعية، لكنه يستخدم فقط لفحوص صغيرة جدا ولا يغير التعقيد التقاربي لحل المسألة الحقيقية.