For a fixed \(n\), the game positions are the coprime ordered pairs \((a,b)\) of positive integers with \(a+b\le n\). A legal move goes to a smaller positive pair \((u,v)\) satisfying
$$1\le u<a,\qquad 1\le v<b,\qquad |av-bu|=1.$$
The game convention used here treats every position with \(a=1\) or \(b=1\) as an immediate win. The goal is to count how many admissible positions are winning when \(n=10^9\).
Let \(W(n)\) be the number of winning positions and \(T(n)\) the number of all primitive positions. The fast solution first counts every primitive pair, then subtracts the pairs that are losing.
Fix the sum \(s=a+b\). Then \(1\le a\le s-1\) and \(b=s-a\), so
$$\gcd(a,b)=\gcd(a,s).$$
Therefore the number of coprime ordered pairs with \(a+b=s\) is exactly \(\varphi(s)\). Summing over every possible total gives
$$T(n)=\sum_{s=2}^{n}\varphi(s)=\Phi(n)-1,$$
where
$$\Phi(n)=\sum_{m\le n}\varphi(m).$$
The implementations evaluate \(\Phi(n)\) through the standard Möbius identity
$$\Phi(n)=\frac{1+\sum_{d=1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor^2}{2},$$
which turns the problem into prefix queries for the Möbius function.
Because the move rule is symmetric in \(a\) and \(b\), it is enough to understand the ordered half \(1<a<b\). Consider such a state and one of its legal children \((u,v)\). From
$$av-bu=\pm1$$
we obtain
$$v-u=\frac{(b-a)u\pm1}{a}\ge 0.$$
So every child also lies in the ordered half, except for the boundary case \((u,v)=(1,1)\), which is already a base win.
Now argue by induction on \(a+b\):
If \(a\) is even, then \(b\) is odd because \(\gcd(a,b)=1\). Reducing \(av-bu=\pm1\) modulo \(2\) gives \(u\equiv1\pmod 2\). Hence every child has odd smaller coordinate, so no child belongs to the losing family described below. Therefore the state is losing.
If \(a\) is odd and \(a>1\), the congruences \(bu\equiv \pm1\pmod a\) give two residues \(u\) and \(a-u\) in \(\{1,\dots,a-1\}\). Since \(a\) is odd, exactly one of them is even. Choosing that even residue produces a legal child with \(u<v\) and, by parity, \(v\) odd. Its smaller coordinate is even, so by induction that child is losing. Therefore the original state is winning.
Thus the losing positions in the ordered half are exactly the primitive pairs
$$ (a,b)=(2x,\,2y+1),\qquad 1\le x\le y,\qquad \gcd(2x,2y+1)=1. $$
Define \(A(q)\) to be the number of pairs of the form \((2x,2y+1)\) with \(1\le x\le y\) and \(2x+2y+1\le q\), ignoring coprimality for the moment. Set
$$s=\left\lfloor\frac{q-1}{2}\right\rfloor.$$
Then the constraints become
$$1\le x\le y,\qquad x+y\le s.$$
For fixed \(x\), the variable \(y\) runs from \(x\) to \(s-x\), so
$$A(q)=\sum_{x=1}^{\lfloor s/2\rfloor}(s-2x+1).$$
This simplifies to the closed form
$$A(q)= \begin{cases} p^2, & s=2p,\\ p(p+1), & s=2p+1. \end{cases}$$
An equivalent version, closer to the implementation, is obtained from \(k=\left\lceil q/2\right\rceil\) and \(p=\left\lfloor k/2\right\rfloor\):
$$A(q)= \begin{cases} p^2, & k\text{ is odd},\\ p(p-1), & k\text{ is even}. \end{cases}$$
Every pair counted by \(A(q)\) has one even coordinate and one odd coordinate, so any common divisor must itself be odd. That makes the Möbius inversion especially clean:
$$L_{1/2}(n)=\sum_{\substack{d\le n\\ d\text{ odd}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right),$$
where \(L_{1/2}(n)\) is the number of losing positions in the ordered half \(a<b\).
To evaluate this quickly, define the ordinary Mertens function
$$M(x)=\sum_{m\le x}\mu(m)$$
and the odd-only prefix
$$M_{\mathrm{odd}}(x)=\sum_{\substack{d\le x\\ d\text{ odd}}}\mu(d).$$
The implementations use the identity
$$M_{\mathrm{odd}}(x)=\sum_{j\ge0} M\!\left(\left\lfloor\frac{x}{2^j}\right\rfloor\right),$$
which follows by expanding the right-hand side and observing that the contributions of even integers cancel in pairs, leaving only odd divisors.
Swapping coordinates preserves both the move rule and the winning/losing status. Since primitive pairs never lie on the diagonal except for \((1,1)\), which is already winning, the total number of losing positions is
$$L(n)=2L_{1/2}(n).$$
Therefore
$$\boxed{W(n)=\left(\sum_{s=2}^{n}\varphi(s)\right)-2\sum_{\substack{d\le n\\ d\text{ odd}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).}$$
This is exactly the arithmetic formula implemented by the fast solution.
First count all primitive states:
$$T(20)=\sum_{s=2}^{20}\varphi(s)=127.$$
Now count the ordered losing shape without enforcing coprimality. Here
$$A(20)=20,$$
coming from the twenty ordered pairs \((2x,2y+1)\) with \(2x<2y+1\) and \(2x+2y+1\le20\).
Among these, the only non-primitive family with odd gcd comes from \(d=3\), because
$$A\!\left(\left\lfloor\frac{20}{3}\right\rfloor\right)=A(6)=1,$$
while \(A(\lfloor20/d\rfloor)=0\) for every larger odd \(d\). Hence
$$L_{1/2}(20)=A(20)-A(6)=20-1=19,$$
$$L(20)=2\cdot19=38,$$
and finally
$$W(20)=127-38=89.$$
This matches direct recursive play on the small instance.
The C++, Python, and Java implementations all follow the same numerical plan. They first build a presieved Möbius table up to a fixed bound and store its prefix sums. That gives instant access to \(M(x)\) for small \(x\).
For larger arguments, the implementation uses the classical divisor-block recurrence
$$M(x)=1-\sum_{l=2}^{x}(r-l+1)\,M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right),$$
where each block \([l,r]\) shares the same quotient \(\left\lfloor x/l\right\rfloor\). Memoization ensures that every large prefix value is computed only once.
The total number of primitive states is then obtained from the summatory-totient identity by grouping equal values of \(\left\lfloor n/d\right\rfloor\). The losing half is evaluated with the same quotient blocking, but using prefix differences of \(M_{\mathrm{odd}}\) and the explicit closed form for \(A(q)\).
After doubling the ordered-half losing count, the implementation subtracts it from the total primitive count. One version also checks the formula on small inputs with direct recursion before printing the large answer, but the actual \(n=10^9\) computation is purely arithmetic.
Let \(B\) be the presieve limit. Building the Möbius sieve and its prefix sums costs \(O(B)\) time and \(O(B)\) memory. The outer summations for both the totient total and the losing count run over the distinct values of \(\left\lfloor n/d\right\rfloor\), which is \(O(\sqrt n)\).
The expensive part is answering large Mertens-prefix queries. Because those queries are memoized and each one is decomposed into quotient blocks as well, the practical running time stays far below linear in \(n\). Memory usage is dominated by the presieve arrays plus the cache of already-computed prefix values.
Für ein festes \(n\) sind die Spielpositionen geordnete teilerfremde Paare \((a,b)\) positiver ganzer Zahlen mit \(a+b\le n\). Ein legaler Zug führt zu einem kleineren positiven Paar \((u,v)\) mit
$$1\le u<a,\qquad 1\le v<b,\qquad |av-bu|=1.$$
Nach der hier verwendeten Spielkonvention ist jede Position mit \(a=1\) oder \(b=1\) sofort gewonnen. Gesucht ist die Anzahl der Gewinnpositionen für \(n=10^9\).
Sei \(W(n)\) die Anzahl der Gewinnpositionen und \(T(n)\) die Anzahl aller primitiven Positionen. Die schnelle Lösung zählt zuerst alle primitiven Paare und zieht dann die Verlustpositionen ab.
Fixiere die Summe \(s=a+b\). Dann gilt \(1\le a\le s-1\) und \(b=s-a\), also
$$\gcd(a,b)=\gcd(a,s).$$
Damit ist die Anzahl teilerfremder geordneter Paare mit \(a+b=s\) genau \(\varphi(s)\). Summiert über alle möglichen Summen ergibt das
$$T(n)=\sum_{s=2}^{n}\varphi(s)=\Phi(n)-1,$$
wobei
$$\Phi(n)=\sum_{m\le n}\varphi(m).$$
Die Implementierungen berechnen \(\Phi(n)\) mit der Standardidentität
$$\Phi(n)=\frac{1+\sum_{d=1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor^2}{2},$$
die das Problem auf Präfixabfragen der Möbiusfunktion reduziert.
Wegen der Symmetrie der Zugregel in \(a\) und \(b\) genügt es, die geordnete Hälfte \(1<a<b\) zu betrachten. Für einen legalen Nachfolger \((u,v)\) gilt aus
$$av-bu=\pm1$$
die Beziehung
$$v-u=\frac{(b-a)u\pm1}{a}\ge 0.$$
Also liegt jeder Nachfolger ebenfalls in der geordneten Hälfte, mit Ausnahme des Randfalls \((u,v)=(1,1)\), der bereits ein Basisgewinn ist.
Nun folgt eine Induktion über \(a+b\):
Ist \(a\) gerade, dann ist \(b\) wegen \(\gcd(a,b)=1\) ungerade. Reduziert man \(av-bu=\pm1\) modulo \(2\), so folgt \(u\equiv1\pmod 2\). Jeder Nachfolger hat also eine ungerade kleinere Koordinate und kann damit nicht zur unten beschriebenen Verlustfamilie gehören. Folglich ist die Position verloren.
Ist \(a\) ungerade und \(a>1\), dann liefern die Kongruenzen \(bu\equiv \pm1\pmod a\) zwei Restklassen \(u\) und \(a-u\) in \(\{1,\dots,a-1\}\). Da \(a\) ungerade ist, ist genau eine davon gerade. Mit dieser geraden Wahl erhält man einen legalen Nachfolger mit \(u<v\), und aus der Parität folgt, dass \(v\) ungerade ist. Seine kleinere Koordinate ist also gerade; nach der Induktion ist dieser Nachfolger verloren. Damit ist die Ausgangsposition gewonnen.
Die Verlustpositionen in der geordneten Hälfte sind daher genau die primitiven Paare
$$ (a,b)=(2x,\,2y+1),\qquad 1\le x\le y,\qquad \gcd(2x,2y+1)=1. $$
Sei \(A(q)\) die Anzahl der Paare der Form \((2x,2y+1)\) mit \(1\le x\le y\) und \(2x+2y+1\le q\), zunächst ohne die Bedingung \(\gcd(2x,2y+1)=1\). Setze
$$s=\left\lfloor\frac{q-1}{2}\right\rfloor.$$
Dann werden die Ungleichungen zu
$$1\le x\le y,\qquad x+y\le s.$$
Für festes \(x\) läuft \(y\) von \(x\) bis \(s-x\), also
$$A(q)=\sum_{x=1}^{\lfloor s/2\rfloor}(s-2x+1).$$
Das vereinfacht sich zu
$$A(q)= \begin{cases} p^2, & s=2p,\\ p(p+1), & s=2p+1. \end{cases}$$
Eine zur Implementierung nähere Form verwendet \(k=\left\lceil q/2\right\rceil\) und \(p=\left\lfloor k/2\right\rfloor\):
$$A(q)= \begin{cases} p^2, & k\text{ ungerade},\\ p(p-1), & k\text{ gerade}. \end{cases}$$
Jedes von \(A(q)\) gezählte Paar hat eine gerade und eine ungerade Koordinate. Ein gemeinsamer Teiler kann deshalb nur ungerade sein. Dadurch erhält man die besonders einfache Inversion
$$L_{1/2}(n)=\sum_{\substack{d\le n\\ d\text{ ungerade}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right),$$
wobei \(L_{1/2}(n)\) die Anzahl der Verlustpositionen in der Hälfte \(a<b\) bezeichnet.
Zur schnellen Auswertung definiert man die gewöhnliche Mertens-Funktion
$$M(x)=\sum_{m\le x}\mu(m)$$
und das auf ungerade Zahlen beschränkte Präfix
$$M_{\mathrm{odd}}(x)=\sum_{\substack{d\le x\\ d\text{ ungerade}}}\mu(d).$$
Die Implementierungen benutzen dafür die Identität
$$M_{\mathrm{odd}}(x)=\sum_{j\ge0} M\!\left(\left\lfloor\frac{x}{2^j}\right\rfloor\right),$$
denn beim Ausmultiplizieren heben sich die Beiträge gerader Zahlen paarweise weg, sodass genau die ungeraden Divisoren übrig bleiben.
Vertauscht man die Koordinaten, bleiben sowohl die Zugregel als auch der Gewinnstatus erhalten. Da primitive Paare außer \((1,1)\) nicht auf der Diagonalen liegen und \((1,1)\) ohnehin gewonnen ist, gilt für die Gesamtzahl der Verlustpositionen
$$L(n)=2L_{1/2}(n).$$
Also
$$\boxed{W(n)=\left(\sum_{s=2}^{n}\varphi(s)\right)-2\sum_{\substack{d\le n\\ d\text{ ungerade}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).}$$
Genau diese arithmetische Formel setzt die schnelle Lösung um.
Zuerst zählen wir alle primitiven Zustände:
$$T(20)=\sum_{s=2}^{20}\varphi(s)=127.$$
Nun zählen wir die geordnete Verlustform zunächst ohne Teilerfremdheit. Hier ist
$$A(20)=20,$$
denn es gibt zwanzig geordnete Paare \((2x,2y+1)\) mit \(2x<2y+1\) und \(2x+2y+1\le20\).
Unter ihnen entsteht die einzige nicht primitive Familie mit ungeradem gemeinsamen Teiler bei \(d=3\), denn
$$A\!\left(\left\lfloor\frac{20}{3}\right\rfloor\right)=A(6)=1,$$
während für jedes größere ungerade \(d\) schon \(A(\lfloor20/d\rfloor)=0\) ist. Also
$$L_{1/2}(20)=A(20)-A(6)=20-1=19,$$
$$L(20)=2\cdot19=38,$$
und damit
$$W(20)=127-38=89.$$
Das stimmt mit direkter rekursiver Auswertung des kleinen Falls überein.
Die C++-, Python- und Java-Implementierungen folgen alle demselben numerischen Schema. Zuerst bauen sie bis zu einer festen Grenze ein vorgesiebtes Möbius-Array samt Präfixsummen auf. Damit lässt sich \(M(x)\) für kleine \(x\) sofort abfragen.
Für größere Argumente wird die klassische Divisor-Block-Rekursion benutzt:
$$M(x)=1-\sum_{l=2}^{x}(r-l+1)\,M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right),$$
wobei jedes Intervall \([l,r]\) denselben Quotienten \(\left\lfloor x/l\right\rfloor\) besitzt. Durch Memoisierung wird jeder große Präfixwert nur ein einziges Mal berechnet.
Die Gesamtzahl primitiver Zustände folgt dann aus der Summenformel für \(\Phi(n)\), wiederum nach Blöcken gleicher Quotienten \(\left\lfloor n/d\right\rfloor\). Die verlorene Hälfte \(L_{1/2}(n)\) wird genauso ausgewertet, nur dass dort Präfixdifferenzen von \(M_{\mathrm{odd}}\) und die geschlossene Formel für \(A(q)\) verwendet werden.
Nach dem Verdoppeln der geordneten Verlustzahl wird sie von der Gesamtzahl primitiver Zustände abgezogen. Eine Version überprüft die Formel zusätzlich auf kleinen Eingaben per direkter Rekursion; die eigentliche Rechnung für \(n=10^9\) ist jedoch vollständig arithmetisch.
Sei \(B\) die Grenze des Vorsiebs. Das Aufbauen der Möbius-Tabelle und ihrer Präfixsummen kostet \(O(B)\) Zeit und \(O(B)\) Speicher. Die äußeren Summen für die Totientensumme und für den Verlustterm laufen über die verschiedenen Werte von \(\left\lfloor n/d\right\rfloor\), also über \(O(\sqrt n)\) Blöcke.
Der teure Teil sind große Mertens-Präfixabfragen. Da diese zwischengespeichert werden und selbst wieder in Quotientenblöcke zerfallen, bleibt die praktische Laufzeit deutlich unter linear in \(n\). Der Speicherverbrauch wird von den Vorsieb-Arrays und dem Cache bereits berechneter Präfixwerte dominiert.
Sabit bir \(n\) için oyun durumları, \(a+b\le n\) koşulunu sağlayan pozitif ve aralarında asal sıralı \((a,b)\) çiftleridir. Geçerli bir hamle,
$$1\le u<a,\qquad 1\le v<b,\qquad |av-bu|=1$$
şartlarını sağlayan daha küçük bir \((u,v)\) çiftine gider. Burada kullanılan oyun kuralına göre \(a=1\) veya \(b=1\) olan her durum anında kazançtır. Amaç, \(n=10^9\) için kaç durumun kazanç olduğunu saymaktır.
\(W(n)\) kazanan durumların, \(T(n)\) ise tüm ilkel durumların sayısı olsun. Hızlı çözüm önce bütün ilkel çiftleri sayar, sonra kaybedenleri çıkarır.
\(s=a+b\) toplamını sabitleyelim. O zaman \(1\le a\le s-1\) ve \(b=s-a\) olduğundan
$$\gcd(a,b)=\gcd(a,s).$$
Dolayısıyla \(a+b=s\) olan aralarında asal sıralı çiftlerin sayısı tam olarak \(\varphi(s)\)'dir. Bütün olası toplamlar üzerinden toplarsak
$$T(n)=\sum_{s=2}^{n}\varphi(s)=\Phi(n)-1,$$
burada
$$\Phi(n)=\sum_{m\le n}\varphi(m).$$
Uygulamalar \(\Phi(n)\)'yi şu klasik Möbius özdeşliğiyle hesaplar:
$$\Phi(n)=\frac{1+\sum_{d=1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor^2}{2}.$$
Böylece problem, Möbius fonksiyonunun önek toplamlarını hızlı sorgulamaya indirgenir.
Hamle kuralı \(a\) ve \(b\) açısından simetrik olduğu için yalnızca \(1<a<b\) sıralı yarısını incelemek yeterlidir. Böyle bir durumun yasal bir çocuğu \((u,v)\) için
$$av-bu=\pm1$$
eşitliğinden
$$v-u=\frac{(b-a)u\pm1}{a}\ge 0$$
elde edilir. Yani her çocuk yine bu sıralı yarıda kalır; tek sınır durumu \((u,v)=(1,1)\) olup o da zaten temel kazançtır.
Şimdi \(a+b\) üzerinden indüksiyon yapalım:
Eğer \(a\) çiftse, \(\gcd(a,b)=1\) nedeniyle \(b\) tektir. \(av-bu=\pm1\) denklemini \(2\) modunda indirgersek \(u\equiv1\pmod 2\) çıkar. Dolayısıyla her çocukta küçük koordinat tektir; bu yüzden aşağıda tarif edilen kaybeden aileye giremez. O halde bu durum kaybedendir.
Eğer \(a\) tek ve \(a>1\) ise, \(bu\equiv \pm1\pmod a\) kongruansları \(\{1,\dots,a-1\}\) içinde \(u\) ve \(a-u\) olmak üzere iki artık sınıf verir. \(a\) tek olduğundan bunlardan tam biri çifttir. Bu çift olan seçim, \(u<v\) sağlayan yasal bir çocuk üretir ve pariteden \(v\)'nin tek olduğu görülür. Böylece küçük koordinatı çift olan bir çocuğa gideriz; indüksiyona göre o çocuk kaybedendir. Bu yüzden başlangıç durumu kazanandır.
Böylece sıralı yarıdaki kaybeden durumlar tam olarak şu ilkel çiftlerdir:
$$ (a,b)=(2x,\,2y+1),\qquad 1\le x\le y,\qquad \gcd(2x,2y+1)=1. $$
\(A(q)\), şimdilik aralarında asallık şartını koymadan, \(1\le x\le y\) ve \(2x+2y+1\le q\) koşullarını sağlayan \((2x,2y+1)\) biçimindeki çiftlerin sayısı olsun. Şunu tanımlayalım:
$$s=\left\lfloor\frac{q-1}{2}\right\rfloor.$$
O zaman kısıtlar
$$1\le x\le y,\qquad x+y\le s$$
haline gelir. Sabit \(x\) için \(y\), \(x\)'ten \(s-x\)'e kadar gider; dolayısıyla
$$A(q)=\sum_{x=1}^{\lfloor s/2\rfloor}(s-2x+1).$$
Bu toplam şu kapalı forma iner:
$$A(q)= \begin{cases} p^2, & s=2p,\\ p(p+1), & s=2p+1. \end{cases}$$
Uygulamaya daha yakın eşdeğer biçimde, \(k=\left\lceil q/2\right\rceil\) ve \(p=\left\lfloor k/2\right\rfloor\) alınırsa
$$A(q)= \begin{cases} p^2, & k\text{ tekse},\\ p(p-1), & k\text{ çiftse}. \end{cases}$$
\(A(q)\) içinde sayılan her çiftte bir koordinat çift, diğeri tektir. Bu yüzden ortak bölen varsa ancak tek olabilir. Bu da çok temiz bir Möbius inversiyonu verir:
$$L_{1/2}(n)=\sum_{\substack{d\le n\\ d\text{ tek}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right),$$
burada \(L_{1/2}(n)\), \(a<b\) yarısındaki kaybeden durum sayısıdır.
Hızlı hesap için sıradan Mertens fonksiyonunu
$$M(x)=\sum_{m\le x}\mu(m)$$
ve yalnızca tekler üzerindeki öneki
$$M_{\mathrm{odd}}(x)=\sum_{\substack{d\le x\\ d\text{ tek}}}\mu(d)$$
tanımlayalım. Uygulamalar şu özdeşliği kullanır:
$$M_{\mathrm{odd}}(x)=\sum_{j\ge0} M\!\left(\left\lfloor\frac{x}{2^j}\right\rfloor\right).$$
Sağ taraf açıldığında çift sayıların katkıları ikili olarak birbirini götürür ve geriye tam olarak tek bölenlerin katkısı kalır.
Koordinatları yer değiştirmek hem hamle kuralını hem de kazanç-kayıp durumunu korur. İlkel çiftler \((1,1)\) dışında köşegen üzerinde bulunmaz; \((1,1)\) de zaten kazanandır. Bu nedenle toplam kaybeden sayısı
$$L(n)=2L_{1/2}(n)$$
olur. Sonuç olarak
$$\boxed{W(n)=\left(\sum_{s=2}^{n}\varphi(s)\right)-2\sum_{\substack{d\le n\\ d\text{ tek}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).}$$
Hızlı çözümün uyguladığı aritmetik formül tam olarak budur.
Önce tüm ilkel durumları sayalım:
$$T(20)=\sum_{s=2}^{20}\varphi(s)=127.$$
Şimdi aralarında asallık koşulu olmadan sıralı kaybeden şekli sayalım. Burada
$$A(20)=20$$
olur; çünkü \(2x<2y+1\) ve \(2x+2y+1\le20\) koşullarını sağlayan yirmi sıralı \((2x,2y+1)\) çifti vardır.
Bunların içindeki tek aralarında asal olmayan aile, ortak tek böleni \(3\) olanlardır; çünkü
$$A\!\left(\left\lfloor\frac{20}{3}\right\rfloor\right)=A(6)=1,$$
ve daha büyük tek \(d\) değerleri için \(A(\lfloor20/d\rfloor)=0\) olur. O halde
$$L_{1/2}(20)=A(20)-A(6)=20-1=19,$$
$$L(20)=2\cdot19=38,$$
ve son olarak
$$W(20)=127-38=89.$$
Bu değer, küçük örnekte doğrudan özyinelemeli oyunla da aynıdır.
C++, Python ve Java uygulamaları aynı sayısal iskeleti kullanır. Önce sabit bir sınıra kadar Möbius değerleri süzülür ve bunların önek toplamları tutulur. Böylece küçük \(x\) için \(M(x)\) anında elde edilir.
Daha büyük girdilerde klasik bölen-blok özyinelemesi kullanılır:
$$M(x)=1-\sum_{l=2}^{x}(r-l+1)\,M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right),$$
burada \([l,r]\) aralığındaki tüm bölenler aynı \(\left\lfloor x/l\right\rfloor\) bölümünü verir. Memoization sayesinde her büyük önek değeri yalnızca bir kez hesaplanır.
Tüm ilkel durumların toplamı, \(\Phi(n)\) özdeşliğinde eşit bölüm blokları gruplanarak bulunur. Kaybeden yarı için aynı bloklama, bu kez \(M_{\mathrm{odd}}\) önek farkları ve \(A(q)\)'nun kapalı formu ile uygulanır.
Sıralı yarıdaki kaybeden sayısı ikiyle çarpılır ve toplam ilkel durum sayısından çıkarılır. Sürümlerden biri büyük cevabı yazmadan önce formülü küçük girdilerde doğrudan özyinelemeli oyunla da doğrular; ancak \(n=10^9\) hesabının kendisi tamamen aritmetiktir.
\(B\) ön süzgeç sınırı olsun. Möbius eleğini ve önek toplamlarını kurmak \(O(B)\) zaman ve \(O(B)\) bellek gerektirir. Hem totient toplamı hem de kaybeden sayımı için dış toplamlar, \(\left\lfloor n/d\right\rfloor\) ifadesinin farklı değerleri üzerinde döner; bunların sayısı \(O(\sqrt n)\)'dir.
Pahalı kısım, büyük Mertens önek sorgularıdır. Bunlar hem önbelleğe alınır hem de yine bölüm-blok ayrışmasıyla hesaplanır. Bu yüzden pratik çalışma süresi \(n\)'e göre doğrusal olmaktan çok daha küçüktür. Bellek kullanımını esas olarak ön süzgeç dizileri ile önbellekte tutulan önek değerleri belirler.
Para un \(n\) fijo, las posiciones del juego son los pares ordenados \((a,b)\) de enteros positivos coprimos con \(a+b\le n\). Un movimiento legal lleva a un par positivo más pequeño \((u,v)\) tal que
$$1\le u<a,\qquad 1\le v<b,\qquad |av-bu|=1.$$
La convención del juego usada aquí considera que toda posición con \(a=1\) o \(b=1\) es ganadora de inmediato. El objetivo es contar cuántas posiciones admisibles son ganadoras cuando \(n=10^9\).
Sea \(W(n)\) el número de posiciones ganadoras y \(T(n)\) el número de todas las posiciones primitivas. La solución rápida primero cuenta todos los pares primitivos y luego resta los que son perdedores.
Fijemos la suma \(s=a+b\). Entonces \(1\le a\le s-1\) y \(b=s-a\), de modo que
$$\gcd(a,b)=\gcd(a,s).$$
Por lo tanto, el número de pares ordenados coprimos con \(a+b=s\) es exactamente \(\varphi(s)\). Sumando sobre todos los valores posibles de \(s\), obtenemos
$$T(n)=\sum_{s=2}^{n}\varphi(s)=\Phi(n)-1,$$
donde
$$\Phi(n)=\sum_{m\le n}\varphi(m).$$
Las implementaciones evalúan \(\Phi(n)\) mediante la identidad clásica de Möbius
$$\Phi(n)=\frac{1+\sum_{d=1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor^2}{2},$$
que reduce el problema a consultas de prefijo de la función de Möbius.
Como la regla del movimiento es simétrica en \(a\) y \(b\), basta estudiar la mitad ordenada \(1<a<b\). Para un hijo legal \((u,v)\) de una posición así, a partir de
$$av-bu=\pm1$$
se deduce
$$v-u=\frac{(b-a)u\pm1}{a}\ge 0.$$
Así, todo hijo también pertenece a la mitad ordenada, salvo el caso límite \((u,v)=(1,1)\), que ya es una victoria base.
Ahora hacemos inducción sobre \(a+b\):
Si \(a\) es par, entonces \(b\) es impar porque \(\gcd(a,b)=1\). Al reducir \(av-bu=\pm1\) módulo \(2\), obtenemos \(u\equiv1\pmod 2\). Por tanto, todo hijo tiene coordenada menor impar y no puede pertenecer a la familia perdedora descrita más abajo. En consecuencia, la posición es perdedora.
Si \(a\) es impar y \(a>1\), las congruencias \(bu\equiv \pm1\pmod a\) producen dos residuos \(u\) y \(a-u\) dentro de \(\{1,\dots,a-1\}\). Como \(a\) es impar, exactamente uno de ellos es par. Eligiendo ese residuo par se obtiene un hijo legal con \(u<v\), y por paridad se ve que \(v\) es impar. Su coordenada menor es entonces par, así que por inducción ese hijo es perdedor. Por ello, la posición original es ganadora.
En consecuencia, las posiciones perdedoras en la mitad ordenada son exactamente los pares primitivos
$$ (a,b)=(2x,\,2y+1),\qquad 1\le x\le y,\qquad \gcd(2x,2y+1)=1. $$
Sea \(A(q)\) el número de pares de la forma \((2x,2y+1)\) con \(1\le x\le y\) y \(2x+2y+1\le q\), ignorando por ahora la condición de coprimalidad. Definimos
$$s=\left\lfloor\frac{q-1}{2}\right\rfloor.$$
Entonces las restricciones se transforman en
$$1\le x\le y,\qquad x+y\le s.$$
Para cada \(x\) fijo, \(y\) recorre desde \(x\) hasta \(s-x\), de modo que
$$A(q)=\sum_{x=1}^{\lfloor s/2\rfloor}(s-2x+1).$$
Esto se simplifica a la forma cerrada
$$A(q)= \begin{cases} p^2, & s=2p,\\ p(p+1), & s=2p+1. \end{cases}$$
Una versión equivalente, más cercana a la implementación, usa \(k=\left\lceil q/2\right\rceil\) y \(p=\left\lfloor k/2\right\rfloor\):
$$A(q)= \begin{cases} p^2, & k\text{ es impar},\\ p(p-1), & k\text{ es par}. \end{cases}$$
Todo par contado por \(A(q)\) tiene una coordenada par y otra impar, así que cualquier divisor común debe ser impar. Eso hace que la inversión de Möbius sea especialmente simple:
$$L_{1/2}(n)=\sum_{\substack{d\le n\\ d\text{ impar}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right),$$
donde \(L_{1/2}(n)\) es el número de posiciones perdedoras en la mitad \(a<b\).
Para evaluarlo con rapidez, definimos la función de Mertens ordinaria
$$M(x)=\sum_{m\le x}\mu(m)$$
y el prefijo restringido a impares
$$M_{\mathrm{odd}}(x)=\sum_{\substack{d\le x\\ d\text{ impar}}}\mu(d).$$
Las implementaciones usan la identidad
$$M_{\mathrm{odd}}(x)=\sum_{j\ge0} M\!\left(\left\lfloor\frac{x}{2^j}\right\rfloor\right),$$
porque al expandir el lado derecho las contribuciones de los enteros pares se cancelan por parejas y solo sobreviven los divisores impares.
Intercambiar las coordenadas conserva tanto la regla del movimiento como el estado ganador o perdedor. Como los pares primitivos no están en la diagonal salvo \((1,1)\), que ya es ganador, el número total de posiciones perdedoras es
$$L(n)=2L_{1/2}(n).$$
Por tanto,
$$\boxed{W(n)=\left(\sum_{s=2}^{n}\varphi(s)\right)-2\sum_{\substack{d\le n\\ d\text{ impar}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).}$$
Esa es exactamente la fórmula aritmética que implementa la solución rápida.
Primero contamos todos los estados primitivos:
$$T(20)=\sum_{s=2}^{20}\varphi(s)=127.$$
Ahora contamos la forma perdedora ordenada sin imponer coprimalidad. Aquí
$$A(20)=20,$$
porque hay veinte pares ordenados \((2x,2y+1)\) con \(2x<2y+1\) y \(2x+2y+1\le20\).
Entre ellos, la única familia no primitiva con divisor común impar aparece para \(d=3\), ya que
$$A\!\left(\left\lfloor\frac{20}{3}\right\rfloor\right)=A(6)=1,$$
mientras que para cualquier impar mayor ya se tiene \(A(\lfloor20/d\rfloor)=0\). Entonces
$$L_{1/2}(20)=A(20)-A(6)=20-1=19,$$
$$L(20)=2\cdot19=38,$$
y finalmente
$$W(20)=127-38=89.$$
Esto coincide con la evaluación recursiva directa del caso pequeño.
Las implementaciones en C++, Python y Java siguen el mismo plan numérico. Primero construyen una tabla presivada de la función de Möbius hasta un límite fijo y almacenan sus sumas prefijo. Con eso, \(M(x)\) se obtiene inmediatamente para valores pequeños de \(x\).
Para argumentos mayores, la implementación usa la recurrencia clásica por bloques de divisores:
$$M(x)=1-\sum_{l=2}^{x}(r-l+1)\,M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right),$$
donde cada intervalo \([l,r]\) comparte el mismo cociente \(\left\lfloor x/l\right\rfloor\). La memoización garantiza que cada valor grande del prefijo se calcule una sola vez.
El número total de estados primitivos se obtiene después con la identidad del sumatorio de la función totiente, agrupando valores iguales de \(\left\lfloor n/d\right\rfloor\). La mitad perdedora se evalúa con la misma técnica de bloques, pero usando diferencias de prefijos de \(M_{\mathrm{odd}}\) y la forma cerrada de \(A(q)\).
Después de duplicar la cuenta de la mitad ordenada, la implementación la resta del total de estados primitivos. Una versión también verifica la fórmula en entradas pequeñas con recursión directa antes de imprimir la respuesta grande, pero el cálculo real para \(n=10^9\) es puramente aritmético.
Sea \(B\) el límite del presieve. Construir la criba de Möbius y sus prefijos cuesta \(O(B)\) tiempo y \(O(B)\) memoria. Las sumas exteriores tanto del total totiente como del conteo perdedor recorren los valores distintos de \(\left\lfloor n/d\right\rfloor\), que son \(O(\sqrt n)\).
La parte costosa es responder las consultas grandes del prefijo de Mertens. Como esas consultas se memoizan y cada una se descompone otra vez en bloques de cocientes, el tiempo práctico queda muy por debajo de una exploración lineal en \(n\). La memoria está dominada por los arreglos del presieve y por la caché de valores prefijo ya calculados.
对固定的 \(n\)，游戏状态是所有满足 \(a+b\le n\) 的正整数有序互素对 \((a,b)\)。一次合法操作会走到一个更小的正整数对 \((u,v)\)，并满足
$$1\le u<a,\qquad 1\le v<b,\qquad |av-bu|=1.$$
这里采用的游戏约定是：只要 \(a=1\) 或 \(b=1\)，该状态立即判为必胜。题目要求统计当 \(n=10^9\) 时，一共有多少个合法状态是必胜状态。
记 \(W(n)\) 为必胜状态数，\(T(n)\) 为全部原始状态数。快速解法的思路是：先把所有互素状态总数算出来，再减去必败状态数。
固定总和 \(s=a+b\)。此时 \(1\le a\le s-1\)，并且 \(b=s-a\)，所以
$$\gcd(a,b)=\gcd(a,s).$$
因此，满足 \(a+b=s\) 的互素有序对个数恰好就是 \(\varphi(s)\)。对所有可能的 \(s\) 求和得到
$$T(n)=\sum_{s=2}^{n}\varphi(s)=\Phi(n)-1,$$
其中
$$\Phi(n)=\sum_{m\le n}\varphi(m).$$
实现中并不是逐项求和，而是使用标准恒等式
$$\Phi(n)=\frac{1+\sum_{d=1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor^2}{2},$$
这样问题就转化为如何高效回答 Möbius 函数的前缀和。
由于走法对 \(a\) 与 \(b\) 完全对称，只需先研究有序半边 \(1<a<b\)。设 \((u,v)\) 是这样一个状态的合法后继。由
$$av-bu=\pm1$$
可得
$$v-u=\frac{(b-a)u\pm1}{a}\ge 0.$$
也就是说，除了边界情况 \((u,v)=(1,1)\) 以外，每个后继仍然落在同一侧的有序区域里，而 \((1,1)\) 本身已经是基础必胜态。
接下来对 \(a+b\) 做归纳：
如果 \(a\) 是偶数，那么因为 \(\gcd(a,b)=1\)，\(b\) 必为奇数。把 \(av-bu=\pm1\) 对 \(2\) 取模，可得 \(u\equiv1\pmod 2\)。因此所有后继的较小坐标都是奇数，所以它们不可能落入下面给出的必败族。于是这个状态本身就是必败态。
如果 \(a\) 是奇数且 \(a>1\)，则同余式 \(bu\equiv \pm1\pmod a\) 会在 \(\{1,\dots,a-1\}\) 中给出两个解 \(u\) 与 \(a-u\)。由于 \(a\) 为奇数，这两个数恰好一奇一偶。选择那个偶数解，就得到一个满足 \(u<v\) 的合法后继，而由奇偶性又可知 \(v\) 为奇数。于是这个后继的较小坐标是偶数，按归纳假设它是必败态，因此原状态必胜。
所以，在有序半边里，必败状态恰好就是下面这些原始对：
$$ (a,b)=(2x,\,2y+1),\qquad 1\le x\le y,\qquad \gcd(2x,2y+1)=1. $$
定义 \(A(q)\) 为满足 \(1\le x\le y\) 且 \(2x+2y+1\le q\) 的形如 \((2x,2y+1)\) 的有序对个数，暂时不要求互素。令
$$s=\left\lfloor\frac{q-1}{2}\right\rfloor.$$
那么约束条件就变成
$$1\le x\le y,\qquad x+y\le s.$$
对固定的 \(x\)，变量 \(y\) 从 \(x\) 取到 \(s-x\)，所以
$$A(q)=\sum_{x=1}^{\lfloor s/2\rfloor}(s-2x+1).$$
这个和可以化成闭式
$$A(q)= \begin{cases} p^2, & s=2p,\\ p(p+1), & s=2p+1. \end{cases}$$
如果想写得更接近实现，可以令 \(k=\left\lceil q/2\right\rceil\)、\(p=\left\lfloor k/2\right\rfloor\)，则
$$A(q)= \begin{cases} p^2, & k\text{ 为奇数},\\ p(p-1), & k\text{ 为偶数}. \end{cases}$$
\(A(q)\) 里计数的每个状态都由一个偶数和一个奇数组成，所以它们的公因子如果存在，只可能是奇数。这使得 Möbius 反演非常直接：
$$L_{1/2}(n)=\sum_{\substack{d\le n\\ d\text{ 为奇数}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right),$$
其中 \(L_{1/2}(n)\) 表示半边 \(a<b\) 中的必败状态数。
为了快速求这个和，先定义普通的 Mertens 函数
$$M(x)=\sum_{m\le x}\mu(m)$$
以及只统计奇数的前缀和
$$M_{\mathrm{odd}}(x)=\sum_{\substack{d\le x\\ d\text{ 为奇数}}}\mu(d).$$
实现使用如下恒等式：
$$M_{\mathrm{odd}}(x)=\sum_{j\ge0} M\!\left(\left\lfloor\frac{x}{2^j}\right\rfloor\right).$$
把右边展开后会发现，所有偶数对应的贡献都会成对抵消，最终只剩下奇数项，这正好就是我们需要的奇数版本前缀和。
交换两个坐标不会改变走法条件，也不会改变胜负性质。原始状态除了 \((1,1)\) 之外不会落在对角线上，而 \((1,1)\) 又已经是必胜态，因此总的必败状态数就是
$$L(n)=2L_{1/2}(n).$$
于是最终答案为
$$\boxed{W(n)=\left(\sum_{s=2}^{n}\varphi(s)\right)-2\sum_{\substack{d\le n\\ d\text{ 为奇数}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).}$$
快速程序实现的正是这条公式。
先统计所有原始状态：
$$T(20)=\sum_{s=2}^{20}\varphi(s)=127.$$
再看不要求互素时的有序必败形状个数。这里有
$$A(20)=20,$$
也就是满足 \(2x<2y+1\) 且 \(2x+2y+1\le20\) 的二十个有序对 \((2x,2y+1)\)。
其中唯一需要扣掉的非原始族来自公因子 \(3\)，因为
$$A\!\left(\left\lfloor\frac{20}{3}\right\rfloor\right)=A(6)=1,$$
而更大的奇数 \(d\) 都已经使得 \(A(\lfloor20/d\rfloor)=0\)。所以
$$L_{1/2}(20)=A(20)-A(6)=20-1=19,$$
$$L(20)=2\cdot19=38,$$
最后得到
$$W(20)=127-38=89.$$
这个结果与小规模递归直接求游戏结果完全一致。
C++、Python 和 Java 实现都遵循同一套数值流程。第一步是在一个固定上界内筛出 Möbius 函数，并保存前缀和数组，这样对较小的 \(x\) 可以立即得到 \(M(x)\)。
对于更大的参数，实现使用经典的按整除分块递推：
$$M(x)=1-\sum_{l=2}^{x}(r-l+1)\,M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right),$$
其中区间 \([l,r]\) 内所有 \(l\) 都对应同一个商 \(\left\lfloor x/l\right\rfloor\)。配合记忆化，每个大的前缀值只会真正计算一次。
总状态数部分使用求和 \(\Phi(n)\) 的恒等式，并按 \(\left\lfloor n/d\right\rfloor\) 的相同取值分块。必败半边的和也是同样的分块结构，只不过那里用的是 \(M_{\mathrm{odd}}\) 的前缀差分，以及 \(A(q)\) 的闭式公式。
最后把半边必败数乘以 \(2\)，再从全部原始状态数中减掉。开发过程里还会在小输入上用直接递归做一致性验证，但真正求 \(n=10^9\) 的那一步完全是算术计算。
设预筛上界为 \(B\)。建立 Möbius 筛和前缀和需要 \(O(B)\) 时间与 \(O(B)\) 空间。无论是总状态数求和还是必败数求和，外层都只遍历 \(\left\lfloor n/d\right\rfloor\) 的不同取值，因此块数是 \(O(\sqrt n)\)。
真正昂贵的是大参数 Mertens 前缀查询。不过这些查询都会被记忆化，而且每一次也都继续按相同的商分块展开，所以实际运行时间远低于线性扫描到 \(n\)。内存主要消耗在预筛数组以及已经缓存的大前缀值上。
Для фиксированного \(n\) позициями игры служат упорядоченные взаимно простые пары положительных чисел \((a,b)\), для которых \(a+b\le n\). Допустимый ход переводит позицию в меньшую положительную пару \((u,v)\), удовлетворяющую условиям
$$1\le u<a,\qquad 1\le v<b,\qquad |av-bu|=1.$$
В принятой здесь игровой конвенции любая позиция с \(a=1\) или \(b=1\) считается немедленно выигрышной. Требуется посчитать число выигрышных позиций при \(n=10^9\).
Обозначим через \(W(n)\) число выигрышных позиций, а через \(T(n)\) число всех примитивных позиций. Быстрое решение сначала считает все взаимно простые пары, а затем вычитает проигрышные.
Зафиксируем сумму \(s=a+b\). Тогда \(1\le a\le s-1\) и \(b=s-a\), поэтому
$$\gcd(a,b)=\gcd(a,s).$$
Следовательно, число взаимно простых упорядоченных пар с \(a+b=s\) равно \(\varphi(s)\). Суммируя по всем возможным \(s\), получаем
$$T(n)=\sum_{s=2}^{n}\varphi(s)=\Phi(n)-1,$$
где
$$\Phi(n)=\sum_{m\le n}\varphi(m).$$
В реализации \(\Phi(n)\) вычисляется с помощью стандартной тождества Мёбиуса
$$\Phi(n)=\frac{1+\sum_{d=1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor^2}{2},$$
сводящего задачу к запросам префиксных сумм функции Мёбиуса.
Поскольку правило хода симметрично по \(a\) и \(b\), достаточно рассмотреть упорядоченную половину \(1<a<b\). Для законного потомка \((u,v)\) такой позиции из равенства
$$av-bu=\pm1$$
следует
$$v-u=\frac{(b-a)u\pm1}{a}\ge 0.$$
То есть каждый потомок тоже лежит в упорядоченной половине, кроме граничного случая \((u,v)=(1,1)\), который уже является базовой выигрышной позицией.
Теперь проводим индукцию по \(a+b\):
Если \(a\) четно, то \(b\) обязано быть нечетным, поскольку \(\gcd(a,b)=1\). Сведя \(av-bu=\pm1\) по модулю \(2\), получаем \(u\equiv1\pmod 2\). Значит, у любого потомка меньшая координата нечетна, и он не может попасть в описываемое ниже проигрышное семейство. Следовательно, исходная позиция проигрышна.
Если \(a\) нечетно и \(a>1\), то сравнения \(bu\equiv \pm1\pmod a\) дают два остатка \(u\) и \(a-u\) из множества \(\{1,\dots,a-1\}\). Так как \(a\) нечетно, один из них четный, а другой нечетный. Выбирая четный остаток, получаем допустимого потомка с \(u<v\); по четности сразу видно, что \(v\) нечетно. Значит, меньшая координата у этого потомка четна, а по индукции такой потомок проигрышен. Следовательно, исходная позиция выигрышна.
Итак, проигрышные позиции в упорядоченной половине — это в точности примитивные пары вида
$$ (a,b)=(2x,\,2y+1),\qquad 1\le x\le y,\qquad \gcd(2x,2y+1)=1. $$
Пусть \(A(q)\) обозначает число пар вида \((2x,2y+1)\) с \(1\le x\le y\) и \(2x+2y+1\le q\), пока без условия \(\gcd(2x,2y+1)=1\). Положим
$$s=\left\lfloor\frac{q-1}{2}\right\rfloor.$$
Тогда ограничения переписываются как
$$1\le x\le y,\qquad x+y\le s.$$
При фиксированном \(x\) переменная \(y\) меняется от \(x\) до \(s-x\), поэтому
$$A(q)=\sum_{x=1}^{\lfloor s/2\rfloor}(s-2x+1).$$
Эта сумма упрощается до закрытой формы
$$A(q)= \begin{cases} p^2, & s=2p,\\ p(p+1), & s=2p+1. \end{cases}$$
Эквивалентная форма, ближе к реализации, использует \(k=\left\lceil q/2\right\rceil\) и \(p=\left\lfloor k/2\right\rfloor\):
$$A(q)= \begin{cases} p^2, & k\text{ нечетно},\\ p(p-1), & k\text{ четно}. \end{cases}$$
У каждой пары, учитываемой функцией \(A(q)\), одна координата четная, а другая нечетная. Поэтому общий делитель, если он есть, может быть только нечетным. Отсюда получается очень удобная формула инверсии:
$$L_{1/2}(n)=\sum_{\substack{d\le n\\ d\text{ нечетно}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right),$$
где \(L_{1/2}(n)\) — число проигрышных позиций в половине \(a<b\).
Для быстрого вычисления вводятся обычная функция Мертенса
$$M(x)=\sum_{m\le x}\mu(m)$$
и префикс только по нечетным числам
$$M_{\mathrm{odd}}(x)=\sum_{\substack{d\le x\\ d\text{ нечетно}}}\mu(d).$$
В реализации используется тождество
$$M_{\mathrm{odd}}(x)=\sum_{j\ge0} M\!\left(\left\lfloor\frac{x}{2^j}\right\rfloor\right),$$
потому что после раскрытия правой части вклады четных чисел попарно сокращаются и остаются только нечетные делители.
Перестановка координат сохраняет и правило хода, и тип позиции. Поскольку примитивные пары, кроме \((1,1)\), не лежат на диагонали, а \((1,1)\) уже выигрышна, общее число проигрышных позиций равно
$$L(n)=2L_{1/2}(n).$$
Следовательно,
$$\boxed{W(n)=\left(\sum_{s=2}^{n}\varphi(s)\right)-2\sum_{\substack{d\le n\\ d\text{ нечетно}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).}$$
Именно эту арифметическую формулу реализует быстрое решение.
Сначала считаем все примитивные состояния:
$$T(20)=\sum_{s=2}^{20}\varphi(s)=127.$$
Теперь посчитаем проигрышную форму без требования взаимной простоты. Здесь
$$A(20)=20,$$
потому что существует двадцать упорядоченных пар \((2x,2y+1)\) с \(2x<2y+1\) и \(2x+2y+1\le20\).
Среди них единственное непримитивное семейство с нечетным общим делителем возникает при \(d=3\), поскольку
$$A\!\left(\left\lfloor\frac{20}{3}\right\rfloor\right)=A(6)=1,$$
а для любого большего нечетного \(d\) уже выполняется \(A(\lfloor20/d\rfloor)=0\). Поэтому
$$L_{1/2}(20)=A(20)-A(6)=20-1=19,$$
$$L(20)=2\cdot19=38,$$
и, наконец,
$$W(20)=127-38=89.$$
Это совпадает с прямым рекурсивным перебором для малого случая.
Реализации на C++, Python и Java используют один и тот же численный план. Сначала до фиксированной границы строится просеянная таблица значений функции Мёбиуса и ее префиксных сумм. Это дает мгновенный доступ к \(M(x)\) для малых \(x\).
Для больших аргументов применяется классическая рекурсия по блокам делителей:
$$M(x)=1-\sum_{l=2}^{x}(r-l+1)\,M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right),$$
где весь интервал \([l,r]\) дает одно и то же значение частного \(\left\lfloor x/l\right\rfloor\). Благодаря мемоизации каждое большое префиксное значение вычисляется лишь один раз.
Общее число примитивных состояний затем получается из тождества для сумматорной функции Эйлера с тем же разбиением по одинаковым значениям \(\left\lfloor n/d\right\rfloor\). Проигрышная половина считается аналогично, но там используются разности префиксов \(M_{\mathrm{odd}}\) и явная формула для \(A(q)\).
После удвоения числа проигрышных позиций в половине реализация вычитает его из общего числа примитивных состояний. Одна из версий также проверяет формулу на малых входах прямой рекурсией, но вычисление для \(n=10^9\) целиком арифметическое.
Пусть \(B\) — граница предварительного просеивания. Построение таблицы Мёбиуса и ее префиксов требует \(O(B)\) времени и \(O(B)\) памяти. Внешние суммы и для тотального числа состояний, и для числа проигрышных позиций проходят по различным значениям \(\left\lfloor n/d\right\rfloor\), а их количество равно \(O(\sqrt n)\).
Самая дорогая часть — запросы больших префиксов функции Мертенса. Но они кешируются, и каждый такой запрос сам разбивается на те же блоки по равным частным. Поэтому практическое время работы остается существенно ниже линейного по \(n\). Память в основном расходуется на массивы предварительного просеивания и на кеш уже вычисленных префиксных значений.
عند تثبيت \(n\)، تكون حالات اللعبة هي الأزواج المرتبة \((a,b)\) من الأعداد الصحيحة الموجبة والمتباينة أوليًا بحيث \(a+b\le n\). والحركة القانونية تنتقل إلى زوج أصغر \((u,v)\) يحقق
$$1\le u<a,\qquad 1\le v<b,\qquad |av-bu|=1.$$
وفق قاعدة اللعبة المستخدمة هنا، فإن كل حالة فيها \(a=1\) أو \(b=1\) تُعد حالة فوز فوري. المطلوب هو عدّ عدد الحالات الرابحة عندما \(n=10^9\).
لنرمز إلى عدد الحالات الرابحة بـ \(W(n)\)، وإلى عدد جميع الحالات الأولية بـ \(T(n)\). الحل السريع يحسب أولًا جميع الأزواج الأولية، ثم يطرح منها الحالات الخاسرة.
ثبّت المجموع \(s=a+b\). عندئذ \(1\le a\le s-1\) و \(b=s-a\)، ولذلك
$$\gcd(a,b)=\gcd(a,s).$$
إذن عدد الأزواج المرتبة المتباينة أوليًا التي تحقق \(a+b=s\) يساوي بالضبط \(\varphi(s)\). وبجمع ذلك على جميع القيم الممكنة لـ \(s\) نحصل على
$$T(n)=\sum_{s=2}^{n}\varphi(s)=\Phi(n)-1,$$
حيث
$$\Phi(n)=\sum_{m\le n}\varphi(m).$$
وتحسب التطبيقات \(\Phi(n)\) باستخدام المتطابقة القياسية لدالة موبيوس
$$\Phi(n)=\frac{1+\sum_{d=1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor^2}{2},$$
وبذلك تتحول المسألة إلى استعلامات سريعة عن المجاميع البادئية لدالة موبيوس.
بما أن قاعدة الحركة متناظرة في \(a\) و\(b\)، فيكفي دراسة النصف المرتب \(1<a<b\). وإذا كانت \((u,v)\) ابنًا قانونيًا لحالة من هذا النوع، فإن العلاقة
$$av-bu=\pm1$$
تعطي
$$v-u=\frac{(b-a)u\pm1}{a}\ge 0.$$
إذن كل ابن يبقى داخل النصف المرتب نفسه، باستثناء الحالة الحدية \((u,v)=(1,1)\)، وهي أصلًا حالة فوز أساسية.
الآن نجري استقراءً على \(a+b\):
إذا كان \(a\) زوجيًا، فإن \(b\) يكون فرديًا لأن \(\gcd(a,b)=1\). وباختزال المعادلة \(av-bu=\pm1\) بترديد \(2\) نحصل على \(u\equiv1\pmod 2\). ومن ثم فإن الإحداثي الأصغر في كل ابن يكون فرديًا، ولذلك لا يمكن أن ينتمي أي ابن إلى العائلة الخاسرة التي سنصفها بعد قليل. لذا تكون الحالة نفسها خاسرة.
أما إذا كان \(a\) فرديًا و\(a>1\)، فإن التطابقين \(bu\equiv \pm1\pmod a\) ينتجان حلين \(u\) و\(a-u\) داخل المجموعة \(\{1,\dots,a-1\}\). ولأن \(a\) فردي فإن أحدهما زوجي والآخر فردي. باختيار الحل الزوجي نحصل على ابن قانوني يحقق \(u<v\)، ومن الزوجية نعرف أيضًا أن \(v\) فردي. وهكذا يكون الإحداثي الأصغر في هذا الابن زوجيًا، وبحسب فرضية الاستقراء يكون هذا الابن خاسرًا، ومن ثم تكون الحالة الأصلية رابحة.
وعليه فإن الحالات الخاسرة في النصف المرتب هي بالضبط الأزواج الأولية من الشكل
$$ (a,b)=(2x,\,2y+1),\qquad 1\le x\le y,\qquad \gcd(2x,2y+1)=1. $$
لنعرّف \(A(q)\) بأنه عدد الأزواج من الشكل \((2x,2y+1)\) التي تحقق \(1\le x\le y\) و\(2x+2y+1\le q\)، مع تجاهل شرط التباين الأولي في هذه المرحلة. ضع
$$s=\left\lfloor\frac{q-1}{2}\right\rfloor.$$
فتصبح القيود
$$1\le x\le y,\qquad x+y\le s.$$
ومع تثبيت \(x\)، يتحرك \(y\) من \(x\) إلى \(s-x\)، ولذلك
$$A(q)=\sum_{x=1}^{\lfloor s/2\rfloor}(s-2x+1).$$
وهذا المجموع يختزل إلى الصيغة المغلقة
$$A(q)= \begin{cases} p^2, & s=2p,\\ p(p+1), & s=2p+1. \end{cases}$$
وهناك صيغة مكافئة أقرب إلى ما تفعله التطبيقات، وذلك بوضع \(k=\left\lceil q/2\right\rceil\) و\(p=\left\lfloor k/2\right\rfloor\):
$$A(q)= \begin{cases} p^2, & k\text{ odd},\\ p(p-1), & k\text{ even}. \end{cases}$$
كل زوج يحسبه \(A(q)\) يملك إحداثيًا زوجيًا وآخر فرديًا، ولهذا فإن أي قاسم مشترك لا بد أن يكون فرديًا. وهنا يصبح عكس موبيوس في غاية البساطة:
$$L_{1/2}(n)=\sum_{\substack{d\le n\\ d\text{ odd}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right),$$
حيث \(L_{1/2}(n)\) هو عدد الحالات الخاسرة في النصف \(a<b\).
ولحساب ذلك بسرعة نعرّف دالة ميرتنز العادية
$$M(x)=\sum_{m\le x}\mu(m)$$
وكذلك المجموع البادئ المقصور على الأعداد الفردية
$$M_{\mathrm{odd}}(x)=\sum_{\substack{d\le x\\ d\text{ odd}}}\mu(d).$$
وتستخدم التطبيقات المتطابقة
$$M_{\mathrm{odd}}(x)=\sum_{j\ge0} M\!\left(\left\lfloor\frac{x}{2^j}\right\rfloor\right),$$
لأن توسيع الطرف الأيمن يُظهر أن مساهمات الأعداد الزوجية تتلاشى زوجًا بزوج، ولا يبقى إلا مساهمات القواسم الفردية.
تبديل الإحداثيين يحافظ على قاعدة الحركة وعلى كون الحالة رابحة أو خاسرة. وبما أن الأزواج الأولية لا تقع على القطر إلا في الحالة \((1,1)\)، وهي أصلًا رابحة، فإن العدد الكلي للحالات الخاسرة يساوي
$$L(n)=2L_{1/2}(n).$$
ومن ثم يكون
$$\boxed{W(n)=\left(\sum_{s=2}^{n}\varphi(s)\right)-2\sum_{\substack{d\le n\\ d\text{ odd}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).}$$
وهذه هي الصيغة الحسابية نفسها التي تنفذها الخوارزمية السريعة.
أولًا نحسب جميع الحالات الأولية:
$$T(20)=\sum_{s=2}^{20}\varphi(s)=127.$$
ثم نعدّ الشكل الخاسر المرتب من دون فرض شرط التباين الأولي. هنا نجد أن
$$A(20)=20,$$
لأن هناك عشرين زوجًا مرتبًا من الشكل \((2x,2y+1)\) يحقق \(2x<2y+1\) و\(2x+2y+1\le20\).
والعائلة الوحيدة غير الأولية ذات القاسم المشترك الفردي تظهر عند \(d=3\)، لأن
$$A\!\left(\left\lfloor\frac{20}{3}\right\rfloor\right)=A(6)=1,$$
بينما يصبح \(A(\lfloor20/d\rfloor)=0\) لكل \(d\) فردي أكبر من ذلك. لذلك
$$L_{1/2}(20)=A(20)-A(6)=20-1=19,$$
$$L(20)=2\cdot19=38,$$
وأخيرًا
$$W(20)=127-38=89.$$
وهذا يطابق الحساب المباشر للعبة على هذا المثال الصغير.
تتبع تطبيقات C++ وPython وJava الخطة العددية نفسها. فهي تبدأ ببناء جدول ممهد مسبقًا لقيم دالة موبيوس حتى حد ثابت، مع تخزين المجاميع البادئية المقابلة. وبذلك يصبح الوصول إلى \(M(x)\) فوريًا عندما يكون \(x\) صغيرًا.
أما عندما تكون القيم كبيرة، فتستخدم الشيفرة علاقة التراجع الكلاسيكية المبنية على تجميع القواسم حسب القيم المتساوية للقسمة الصحيحة:
$$M(x)=1-\sum_{l=2}^{x}(r-l+1)\,M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right),$$
حيث تشترك كل القيم داخل الفترة \([l,r]\) في نفس الخارج \(\left\lfloor x/l\right\rfloor\). ومع التخزين التذكري لا يُحسب كل مجموع بادئ كبير إلا مرة واحدة فقط.
بعد ذلك يُستخرج العدد الكلي للحالات الأولية من متطابقة مجموع دالة أويلر باستخدام تجميع القيم المتساوية لـ \(\left\lfloor n/d\right\rfloor\). ويُحسب نصف الحالات الخاسرة بالطريقة نفسها، لكن مع فروق المجاميع البادئية لـ \(M_{\mathrm{odd}}\) ومع الصيغة المغلقة للدالة \(A(q)\).
ثم يُضاعف عدد الحالات الخاسرة في النصف المرتب ويُطرح من العدد الكلي للحالات الأولية. كما تتضمن إحدى النسخ فحصًا صغيرًا بالاستدعاء التراجعي على قيم صغيرة قبل طباعة النتيجة الكبرى، لكن حساب \(n=10^9\) نفسه حساب عددي صرف.
ليكن \(B\) هو حد الغربلة المسبقة. بناء جدول موبيوس ومجاميعه البادئية يحتاج إلى زمن \(O(B)\) وذاكرة \(O(B)\). أما المجاميع الخارجية في كل من جزء المجموع الكلي وجزء الحالات الخاسرة، فهي تمر فقط على القيم المختلفة لـ \(\left\lfloor n/d\right\rfloor\)، وعدد هذه القيم يساوي \(O(\sqrt n)\).
الجزء الأكثر كلفة هو الإجابة عن استعلامات المجاميع البادئية الكبيرة لدالة ميرتنز. ولكن هذه الاستعلامات تُخزَّن، وكل واحد منها يُفكك هو الآخر إلى كتل قسمة متساوية، لذلك يبقى الزمن العملي أقل بكثير من المسح الخطي حتى \(n\). ويهيمن على الذاكرة كل من مصفوفات الغربلة المسبقة وجدول القيم البادئية المحسوبة مسبقًا.