We consider ordered piles \((x,y)\) with
$$1\le x \lt y \le N.$$
In each move, a player subtracts a positive multiple of the smaller pile from the larger pile, and the result must remain nonnegative. The player who takes the last stone wins. The problem asks for the sum of \(x+y\) over all losing pairs with \(1\le x \lt y\le N\):
$$S(N)=\sum (x+y).$$
for the enormous value
$$N=10^{16},$$
with the final answer reported modulo
$$7^{10}=282475249.$$
1) First isolate the easy winning cases.
If \(y\ge 2x\), then the larger pile contains at least two copies of the smaller one, so the current player has several legal Euclid-style subtractions and can force a win immediately. Likewise, if \(x\mid y\), the current player can reduce to a terminal multiple situation. Therefore the only subtle region is
$$x \lt y \lt 2x,\qquad x\nmid y.$$
2) Inside that strip there is only one move.
When \(x \lt y \lt 2x\), the only allowed multiple is exactly one copy of the smaller pile. So the game moves deterministically to
$$ (x,y)\longrightarrow (y-x,x), $$
after reordering the two piles. This is just one step of Euclid's algorithm.
3) Losing positions form a golden-ratio interval.
Write \(y=x+d\) with
$$1\le d \lt x.$$
By the previous step, \((x,x+d)\) is losing exactly when \((d,x)\) is winning. Inductively, the losing positions are characterized by the sharp Beatty boundary
$$x \lt y \le \lfloor \varphi x\rfloor,$$
where
$$\varphi=\frac{1+\sqrt5}{2}.$$
Equivalently, for a fixed \(x\), the admissible differences are
$$1\le d\le a_x,\qquad a_x=\left\lfloor\frac{x}{\varphi}\right\rfloor.$$
The equality of the two forms comes from
$$\varphi=1+\frac{1}{\varphi},\qquad \lfloor \varphi x\rfloor=x+\left\lfloor \frac{x}{\varphi}\right\rfloor.$$
4) Convert the weighted sum to a double sum.
For each fixed \(x\), the losing values are
$$y=x+1,\ x+2,\ \dots,\ x+a_x,$$
unless the global bound \(y\le N\) truncates them. Therefore
$$S(N)=\sum_{x=1}^{N}\sum_{d=1}^{\min(a_x,N-x)}(x+(x+d))$$
or
$$S(N)=\sum_{x=1}^{N}\sum_{d=1}^{\min(a_x,N-x)}(2x+d).$$
5) Prefix-tail split.
Define the cutoff
$$c=\left\lfloor\frac{N+1}{\varphi}\right\rfloor.$$
If \(x\le c\), then the full losing interval still fits below \(N\), because \(x+a_x\le N\). If \(x\gt c\), the interval is cut short by the ceiling \(N\). Hence
$$S(N)=S_{\text{pref}}+S_{\text{tail}}.$$
6) The prefix depends on three Beatty sums.
For \(x\le c\), the inner sum is
$$\sum_{d=1}^{a_x}(2x+d)=2x\,a_x+\frac{a_x(a_x+1)}{2}.$$
Now define
$$G(n)=\sum_{k=1}^{n} a_k,\qquad P(n)=\sum_{k=1}^{n} k\,a_k,\qquad Q(n)=\sum_{k=1}^{n} a_k^2.$$
Then
$$S_{\text{pref}}=\sum_{x=1}^{c}\left(2x\,a_x+\frac{a_x(a_x+1)}{2}\right)=\frac{4P(c)+Q(c)+G(c)}{2}.$$
7) Why \(G,P,Q\) can be computed recursively.
Let
$$m=\left\lfloor\frac{n}{\varphi}\right\rfloor.$$
Classical Beatty partition identities allow us to rewrite the sums up to \(n\) in terms of the same sums up to \(m\). The code uses the exact recurrences
$$G(n)=nm-\frac{m(m+1)}{2}-G(m),$$
$$Q(n)=nm^2-2\sum_{k=1}^{m}k^2-2P(m)+\frac{m(m+1)}{2}+G(m),$$
$$P(n)=\frac{nm(n+1)}{2}-\frac{\left(\sum_{k=1}^{m}k^2+2P(m)+Q(m)+\frac{m(m+1)}{2}+G(m)\right)}{2}.$$
Each recursive step replaces \(n\) by approximately \(n/\varphi\), so the depth is only logarithmic.
8) The tail becomes an ordinary polynomial sum.
For \(x\gt c\), the upper limit is no longer \(a_x\), but \(N-x\). So the inner sum becomes
$$\sum_{d=1}^{N-x}(2x+d)=2x(N-x)+\frac{(N-x)(N-x+1)}{2}.$$
Summing this over \(x=c+1,\dots,N\) reduces the tail to combinations of
$$\sum x,\qquad \sum x^2,$$
which the code evaluates in closed form.
9) Worked example \(N=10\).
The losing pairs are
$$(2,3),(3,4),(4,5),(4,6),(5,6),(5,7),(5,8),(6,7),(6,8),(6,9),$$
$$(7,8),(7,9),(7,10),(8,9),(8,10),(9,10).$$
Their weighted sum is
$$S(10)=211,$$
which matches the checkpoint in the program.
1) Use the golden-ratio characterization of losing positions.
2) Split the total sum at \(c=\lfloor (N+1)/\varphi\rfloor\).
3) Evaluate the prefix via the recursive Beatty sums \(G,P,Q\).
4) Evaluate the tail via polynomial formulas for \(\sum x\) and \(\sum x^2\).
5) Do the same computation modulo \(7^{10}\) for the final output.
Because each Beatty recursion step shrinks \(n\) to roughly \(n/\varphi\), the depth is
$$O(\log N).$$
Each level performs only constant-time big-integer or modular arithmetic, so the whole method is extremely fast even for \(N=10^{16}\).
The code checks
$$S(10)=211,\qquad S(10^4)=230312207313.$$
It also verifies that exact arithmetic and arithmetic modulo \(7^{10}\) agree for \(N=10^6\).
For the target value
$$N=10^{16},$$
the final answer modulo \(7^{10}\) is
$$54672965.$$
Gegeben sind Steinpaare \((x,y)\) mit
$$1\le x \lt y\le N.$$
In einem Zug wird ein positives Vielfaches des kleineren Stapels vom groesseren abgezogen. Wer den letzten Stein nimmt, gewinnt. Gesucht ist die Summe von \(x+y\) ueber alle Verliererpaare mit \(1\le x \lt y\le N\):
$$S(N)=\sum (x+y).$$
fuer
$$N=10^{16},$$
wobei die Endausgabe modulo
$$7^{10}=282475249$$
erfolgt.
1) Die einfachen Gewinnfaelle.
Ist \(y\ge 2x\), dann kann der aktuelle Spieler sofort ein geeignetes Vielfaches von \(x\) abziehen. Ist \(x\mid y\), liegt ebenfalls ein unmittelbarer Gewinnzug vor. Interessant ist also nur der Streifen
$$x \lt y \lt 2x.$$
2) In diesem Streifen gibt es nur einen Zug.
Wenn \(x \lt y \lt 2x\), darf man genau einmal den kleineren Stapel abziehen. Damit geht der Zustand nach Umordnung ueber in
$$ (x,y)\to(y-x,x). $$
3) Goldener-Ratio-Rand.
Schreibe \(y=x+d\). Dann liegt eine Verliererposition genau dann vor, wenn
$$x \lt y \le \lfloor \varphi x\rfloor,$$
also aequivalent
$$1\le d\le a_x,\qquad a_x=\left\lfloor\frac{x}{\varphi}\right\rfloor,$$
mit
$$\varphi=\frac{1+\sqrt5}{2}.$$
4) Doppelsumme.
Somit
$$S(N)=\sum_{x=1}^{N}\sum_{d=1}^{\min(a_x,N-x)}(2x+d).$$
5) Prefix und Tail.
Mit
$$c=\left\lfloor\frac{N+1}{\varphi}\right\rfloor$$
gilt: Fuer \(x\le c\) passt das ganze Verliererintervall unter \(y\le N\), fuer \(x\gt c\) wird es durch \(N-x\) abgeschnitten.
6) Drei Beatty-Summen.
Definiere
$$G(n)=\sum_{k=1}^{n} a_k,\qquad P(n)=\sum_{k=1}^{n}k a_k,\qquad Q(n)=\sum_{k=1}^{n} a_k^2.$$
Dann ist der Praefixteil
$$S_{\text{pref}}=\sum_{x=1}^{c}\left(2x a_x+\frac{a_x(a_x+1)}{2}\right)=\frac{4P(c)+Q(c)+G(c)}{2}.$$
7) Rekursion mit \(m=\lfloor n/\varphi\rfloor\).
Der Code benutzt die Beatty-Identitaeten
$$G(n)=nm-\frac{m(m+1)}{2}-G(m),$$
$$Q(n)=nm^2-2\sum_{k=1}^{m}k^2-2P(m)+\frac{m(m+1)}{2}+G(m),$$
$$P(n)=\frac{nm(n+1)}{2}-\frac{\left(\sum_{k=1}^{m}k^2+2P(m)+Q(m)+\frac{m(m+1)}{2}+G(m)\right)}{2}.$$
Jeder Rekursionsschritt schrumpft das Problem um etwa den Faktor \(\varphi\).
8) Der Tail ist elementar.
Fuer \(x\gt c\) lautet die innere Summe
$$2x(N-x)+\frac{(N-x)(N-x+1)}{2},$$
also nur noch eine Kombination aus \(\sum x\) und \(\sum x^2\).
9) Beispiel \(N=10\).
Die gewichtete Summe aller Verliererpositionen ist
$$S(10)=211,$$
genau wie im Checkpoint des Programms.
1) Charakterisiere Verliererpositionen ueber \(a_x=\lfloor x/\varphi\rfloor\).
2) Zerlege bei \(c=\lfloor (N+1)/\varphi\rfloor\).
3) Berechne den Praefixteil ueber \(G,P,Q\).
4) Berechne den Tail ueber geschlossene Polynomsummen.
5) Fuehre die gleiche Rechnung modulo \(7^{10}\) aus.
Die Tiefe der Beatty-Rekursion ist
$$O(\log N).$$
Pro Ebene faellt nur konstante Grosszahl- bzw. Modulo-Arithmetik an.
Geprueft werden
$$S(10)=211,\qquad S(10^4)=230312207313.$$
Fuer \(N=10^{16}\) ergibt sich modulo \(7^{10}\)
$$54672965.$$
Sirali tas yiginlari \((x,y)\) icin
$$1\le x \lt y \le N$$
durumlarini inceliyoruz. Her hamlede buyuk yigindan, kucuk yigini pozitif tam kati kadar tas cikariliyor. Son tasi alan oyuncu kazaniyor. Soru, \(1\le x \lt y\le N\) kosulundaki tum kaybeden ciftler icin \(x+y\) toplamini soruyor:
$$S(N)=\sum (x+y).$$
Burada
$$N=10^{16},$$
ve cevap
$$7^{10}=282475249$$
modunda isteniyor.
1) Once kolay kazanan durumlari ayiralim.
Eger \(y\ge 2x\) ise buyuk yigin kucugun en az iki kati oldugu icin oyuncu uygun bir kat kadar cikarma yaparak kontrolu alabilir. Eger \(x\mid y\) ise yine dogrudan kazandiran bir hamle vardir. Demek ki asil ilginc bolge
$$x \lt y \lt 2x$$
serididir.
2) Bu seritte yalnizca tek hamle vardir.
\(x \lt y \lt 2x\) iken buyuk yigindan kucugun ancak bir kati cikartilabilir. Bu yuzden oyun zorunlu olarak
$$ (x,y)\to(y-x,x) $$
durumuna gider; sonra yigini tekrar siralariz.
3) Kaybeden bolge altin oranla cizilir.
\(y=x+d\) yazalim. O zaman kaybeden konumlar tam olarak
$$x \lt y \le \lfloor \varphi x\rfloor$$
kosulunu saglar. Burada
$$\varphi=\frac{1+\sqrt5}{2}.$$
Esdeger bicimde, sabit bir \(x\) icin farklar
$$1\le d\le a_x,\qquad a_x=\left\lfloor\frac{x}{\varphi}\right\rfloor$$
araligindadir. Cunku
$$\varphi=1+\frac1\varphi,\qquad \lfloor \varphi x\rfloor=x+\left\lfloor\frac{x}{\varphi}\right\rfloor.$$
4) Agirlikli toplam cift toplama donusur.
Kaybeden \(y\) degerleri
$$y=x+1,\ x+2,\ \dots,\ x+a_x$$
seklindedir; ama global sinir \(y\le N\) bunu kisabilir. Dolayisiyla
$$S(N)=\sum_{x=1}^{N}\sum_{d=1}^{\min(a_x,N-x)}(2x+d).$$
5) Prefix ve tail ayrimi.
Kesim noktasi
$$c=\left\lfloor\frac{N+1}{\varphi}\right\rfloor$$
olsun. \(x\le c\) icin tam kaybeden araligi \(y\le N\) icine sigar. \(x \gt c\) icin ise ust sinir \(N-x\) tarafindan kirpilir. Bu nedenle
$$S(N)=S_{\text{pref}}+S_{\text{tail}}.$$
6) Prefix kismi uc Beatty toplami ile yazilir.
\(x\le c\) icin ic toplam
$$\sum_{d=1}^{a_x}(2x+d)=2x a_x+\frac{a_x(a_x+1)}{2}$$
olur. Simdi
$$G(n)=\sum_{k=1}^{n}a_k,\qquad P(n)=\sum_{k=1}^{n}k a_k,\qquad Q(n)=\sum_{k=1}^{n}a_k^2$$
tanimlarini yaparsak
$$S_{\text{pref}}=\frac{4P(c)+Q(c)+G(c)}{2}$$
elde edilir.
7) \(G,P,Q\) neden hizli hesaplanabiliyor?
Su degiskeni alalim:
$$m=\left\lfloor\frac{n}{\varphi}\right\rfloor.$$
Klasik Beatty parcalama ozdeslikleri sayesinde kod su reküranslari kullaniyor:
$$G(n)=nm-\frac{m(m+1)}{2}-G(m),$$
$$Q(n)=nm^2-2\sum_{k=1}^{m}k^2-2P(m)+\frac{m(m+1)}{2}+G(m),$$
$$P(n)=\frac{nm(n+1)}{2}-\frac{\left(\sum_{k=1}^{m}k^2+2P(m)+Q(m)+\frac{m(m+1)}{2}+G(m)\right)}{2}.$$
Her adimda arguman yaklasik \(n/\varphi\) seviyesine dusuyor; yani derinlik logaritmik.
8) Tail kismi artik polinom toplamidir.
\(x \gt c\) icin ust sinir \(a_x\) degil \(N-x\) oldugu icin
$$\sum_{d=1}^{N-x}(2x+d)=2x(N-x)+\frac{(N-x)(N-x+1)}{2}$$
olur. Bunun \(x\) uzerinden toplami sadece \(\sum x\) ve \(\sum x^2\) ile ifade edilir; kodun `tail` kismi tam bunu yapiyor.
9) Kucuk ornek: \(N=10\).
Kaybeden ciftlerin agirlikli toplami
$$S(10)=211$$
cikar. Kod bunu checkpoint olarak kullanir.
1) Kaybeden konumlari \(a_x=\lfloor x/\varphi\rfloor\) ile karakterize et.
2) Toplami \(c=\lfloor (N+1)/\varphi\rfloor\) noktasinda ikiye ayir.
3) Prefix kismini \(G,P,Q\) ile hesapla.
4) Tail kismini kapali polinom formulleriyle hesapla.
5) Sonucu mod \(7^{10}\) icin de ayni yapiyla hesapla.
Beatty reküransi her seferinde boyutu yaklasik \(\varphi\) faktoruyla kuculttugu icin derinlik
$$O(\log N)$$
olur. Her seviyede sabit sayida buyuk tamsayi veya moduler islem yapilir.
Kod su degerleri dogrular:
$$S(10)=211,\qquad S(10^4)=230312207313.$$
Ayrica \(N=10^6\) icin tam hesap ile mod \(7^{10}\) hesabinin uyumlu oldugunu kontrol eder.
Hedef deger
$$N=10^{16}$$
icin mod \(7^{10}\) sonucu
$$54672965$$
olarak bulunur.
Consideramos pares ordenados \((x,y)\) con
$$1\le x \lt y\le N.$$
En cada turno se resta del monton mayor un multiplo positivo del menor. Gana quien toma la ultima piedra. Debemos calcular la suma de \(x+y\) sobre todos los pares perdedores con \(1\le x \lt y\le N\):
$$S(N)=\sum (x+y).$$
para
$$N=10^{16},$$
y devolver la respuesta modulo
$$7^{10}=282475249.$$
1) Casos ganadores inmediatos.
Si \(y\ge 2x\), el jugador actual puede restar una cantidad adecuada y forzar la victoria. Si \(x\mid y\), tambien hay una jugada ganadora inmediata. Por tanto, la franja no trivial es
$$x \lt y \lt 2x.$$
2) En esa franja solo hay una jugada.
Cuando \(x \lt y \lt 2x\), solo se puede restar una copia del monton pequeno. El estado pasa entonces a
$$ (x,y)\to(y-x,x), $$
tras reordenar los montones.
3) La frontera con razon aurea.
Escribiendo \(y=x+d\), las posiciones perdedoras satisfacen exactamente
$$x \lt y \le \lfloor \varphi x\rfloor,$$
donde
$$\varphi=\frac{1+\sqrt5}{2}.$$
Equivalentemente, para cada \(x\),
$$1\le d\le a_x,\qquad a_x=\left\lfloor\frac{x}{\varphi}\right\rfloor.$$
4) Reescribir la suma.
Luego
$$S(N)=\sum_{x=1}^{N}\sum_{d=1}^{\min(a_x,N-x)}(2x+d).$$
5) Separacion en prefijo y cola.
Definimos
$$c=\left\lfloor\frac{N+1}{\varphi}\right\rfloor.$$
Para \(x\le c\), el intervalo perdedor completo cabe en \(y\le N\). Para \(x \gt c\), se recorta por \(N-x\).
6) Tres sumas de Beatty.
Sean
$$G(n)=\sum_{k=1}^{n} a_k,\qquad P(n)=\sum_{k=1}^{n}k a_k,\qquad Q(n)=\sum_{k=1}^{n} a_k^2.$$
Entonces
$$S_{\text{pref}}=\frac{4P(c)+Q(c)+G(c)}{2}.$$
7) Recursion de Beatty.
Con
$$m=\left\lfloor\frac{n}{\varphi}\right\rfloor,$$
el codigo usa relaciones recursivas para \(G,P,Q\) que reducen el tamano a aproximadamente \(n/\varphi\) en cada paso.
8) La cola es polinomial.
Para \(x \gt c\), la suma interior se convierte en
$$2x(N-x)+\frac{(N-x)(N-x+1)}{2},$$
que solo depende de \(\sum x\) y \(\sum x^2\).
9) Ejemplo \(N=10\).
La suma ponderada de las posiciones perdedoras vale
$$S(10)=211,$$
que coincide con el checkpoint del programa.
1) Caracterizar las posiciones perdedoras mediante \(a_x=\lfloor x/\varphi\rfloor\).
2) Cortar en \(c=\lfloor (N+1)/\varphi\rfloor\).
3) Calcular el prefijo usando \(G,P,Q\).
4) Calcular la cola con formulas cerradas para \(\sum x\) y \(\sum x^2\).
5) Repetir el mismo esquema modulo \(7^{10}\).
La profundidad recursiva es
$$O(\log N),$$
y en cada nivel solo hay un numero constante de operaciones aritmeticas grandes o modulares.
El codigo verifica
$$S(10)=211,\qquad S(10^4)=230312207313.$$
Para
$$N=10^{16}$$
la respuesta final modulo \(7^{10}\) es
$$54672965.$$
考虑满足
$$1\le x \lt y\le N$$
的石子堆 \((x,y)\)。每一步都要从较大的那堆里减去较小那堆的某个正整数倍。拿走最后一颗石子的人获胜。题目要求对所有满足 \(1\le x \lt y\le N\) 的必败对把 \(x+y\) 加起来：
$$S(N)=\sum (x+y).$$
其中
$$N=10^{16},$$
并最终对
$$7^{10}=282475249$$
取模。
1) 先找显然的必胜区。
如果 \(y\ge 2x\)，当前玩家可以减去合适的倍数立刻占优；如果 \(x\mid y\)，也存在直接获胜的 Euclid 型操作。所以真正麻烦的只是在
$$x \lt y \lt 2x$$
这一条带里。
2) 在这条带里只有一个合法动作。
当 \(x \lt y \lt 2x\) 时，只能减去一次较小堆，于是状态必然变成
$$ (x,y)\to(y-x,x), $$
然后再重新排序。
3) 必胜/必败边界由黄金分割给出。
写成 \(y=x+d\)。则必败位置恰好满足
$$x \lt y \le \lfloor \varphi x\rfloor,$$
其中
$$\varphi=\frac{1+\sqrt5}{2}.$$
等价地，对固定 \(x\)，允许的差值范围是
$$1\le d\le a_x,\qquad a_x=\left\lfloor\frac{x}{\varphi}\right\rfloor.$$
4) 把目标写成双重求和。
于是
$$S(N)=\sum_{x=1}^{N}\sum_{d=1}^{\min(a_x,N-x)}(2x+d).$$
5) 前缀与尾部分裂。
定义
$$c=\left\lfloor\frac{N+1}{\varphi}\right\rfloor.$$
当 \(x\le c\) 时，完整的必败区间都落在 \(y\le N\) 内；当 \(x \gt c\) 时，会被上界 \(N-x\) 截断。
6) 三个 Beatty 和。
记
$$G(n)=\sum_{k=1}^{n} a_k,\qquad P(n)=\sum_{k=1}^{n}k a_k,\qquad Q(n)=\sum_{k=1}^{n} a_k^2.$$
则前缀部分是
$$S_{\text{pref}}=\frac{4P(c)+Q(c)+G(c)}{2}.$$
7) 为什么 \(G,P,Q\) 可以递归计算。
令
$$m=\left\lfloor\frac{n}{\varphi}\right\rfloor.$$
利用经典 Beatty 分割恒等式，代码把 \(G(n),P(n),Q(n)\) 全部改写成 \(m\) 处的同类量，因此规模每次缩小到大约 \(n/\varphi\)。这就是整体只需对数层递归的原因。
8) 尾部退化为普通多项式和。
对 \(x \gt c\)，内层上界变成 \(N-x\)，所以
$$\sum_{d=1}^{N-x}(2x+d)=2x(N-x)+\frac{(N-x)(N-x+1)}{2}.$$
再对 \(x\) 求和，只需要 \(\sum x\) 和 \(\sum x^2\) 即可。
9) 小例子 \(N=10\).
程序中的校验值是
$$S(10)=211.$$
1) 用 \(a_x=\lfloor x/\varphi\rfloor\) 描述所有必败位置。
2) 在 \(c=\lfloor (N+1)/\varphi\rfloor\) 处分成前缀与尾部。
3) 前缀部分通过递归计算 \(G,P,Q\)。
4) 尾部通过 \(\sum x\)、\(\sum x^2\) 的闭式计算。
5) 最终在模 \(7^{10}\) 下输出结果。
递归深度为
$$O(\log N),$$
每层只做常数次大整数或模运算，因此即使 \(N=10^{16}\) 也很快。
代码验证
$$S(10)=211,\qquad S(10^4)=230312207313.$$
对于
$$N=10^{16},$$
最终答案模 \(7^{10}\) 为
$$54672965.$$
Рассматриваются пары куч \((x,y)\) с
$$1\le x \lt y\le N.$$
За ход из большей кучи вычитается положительное кратное меньшей. Побеждает тот, кто забирает последний камень. Нужно найти сумму \(x+y\) по всем проигрышным парам с \(1\le x \lt y\le N\):
$$S(N)=\sum (x+y).$$
для
$$N=10^{16},$$
а итог дать по модулю
$$7^{10}=282475249.$$
1) Простые выигрышные случаи.
Если \(y\ge 2x\), текущий игрок может сразу сделать подходящее евклидово вычитание. Если \(x\mid y\), выигрыш тоже немедленный. Поэтому тонкая часть игры лежит только в полосе
$$x \lt y \lt 2x.$$
2) В этой полосе ход единственный.
Когда \(x \lt y \lt 2x\), можно вычесть лишь одну копию меньшей кучи, и состояние переходит в
$$ (x,y)\to(y-x,x), $$
после переупорядочивания.
3) Граница через золотое сечение.
Пусть \(y=x+d\). Тогда проигрышные позиции описываются условием
$$x \lt y \le \lfloor \varphi x\rfloor,$$
где
$$\varphi=\frac{1+\sqrt5}{2}.$$
Эквивалентно, для фиксированного \(x\)
$$1\le d\le a_x,\qquad a_x=\left\lfloor\frac{x}{\varphi}\right\rfloor.$$
4) Двойная сумма.
Отсюда
$$S(N)=\sum_{x=1}^{N}\sum_{d=1}^{\min(a_x,N-x)}(2x+d).$$
5) Префикс и хвост.
Положим
$$c=\left\lfloor\frac{N+1}{\varphi}\right\rfloor.$$
Для \(x\le c\) весь проигрышный интервал помещается под ограничением \(y\le N\). Для \(x \gt c\) он обрезается сверху условием \(N-x\).
6) Три Beatty-суммы.
Вводим
$$G(n)=\sum_{k=1}^{n} a_k,\qquad P(n)=\sum_{k=1}^{n}k a_k,\qquad Q(n)=\sum_{k=1}^{n} a_k^2.$$
Тогда префиксная часть равна
$$S_{\text{pref}}=\frac{4P(c)+Q(c)+G(c)}{2}.$$
7) Рекурсия по Beatty.
При
$$m=\left\lfloor\frac{n}{\varphi}\right\rfloor$$
код рекурсивно выражает \(G(n),P(n),Q(n)\) через соответствующие суммы в точке \(m\). На каждом шаге аргумент уменьшается примерно в \(\varphi\) раз.
8) Хвостовая часть элементарна.
Для \(x \gt c\) внутренняя сумма имеет вид
$$2x(N-x)+\frac{(N-x)(N-x+1)}{2},$$
то есть всё сводится к \(\sum x\) и \(\sum x^2\).
9) Пример \(N=10\).
Контрольное значение:
$$S(10)=211.$$
1) Описать проигрышные позиции через \(a_x=\lfloor x/\varphi\rfloor\).
2) Разбить сумму в точке \(c=\lfloor (N+1)/\varphi\rfloor\).
3) Посчитать префикс через \(G,P,Q\).
4) Посчитать хвост закрытыми формулами.
5) Повторить вычисление по модулю \(7^{10}\).
Глубина рекурсии равна
$$O(\log N),$$
а на каждом уровне выполняется лишь постоянное число операций с большими числами или по модулю.
Проверяются значения
$$S(10)=211,\qquad S(10^4)=230312207313.$$
Для
$$N=10^{16}$$
итог по модулю \(7^{10}\) равен
$$54672965.$$
ننظر إلى زوجي كومتين \((x,y)\) بحيث
$$1\le x \lt y\le N.$$
في كل دور يطرح اللاعب من الكومة الأكبر مضاعفًا صحيحًا موجبًا للكومة الأصغر. من يأخذ آخر حجر يفوز. المطلوب هو جمع \(x+y\) على جميع الأزواج الخاسرة التي تحقق \(1\le x \lt y\le N\):
$$S(N)=\sum (x+y).$$
عندما
$$N=10^{16},$$
ثم إعطاء الجواب بترديد
$$7^{10}=282475249.$$
1) الحالات الرابحة السهلة.
إذا كان \(y\ge 2x\) فهناك طرح مناسب يعطي اللاعب الحالي أفضلية مباشرة. وإذا كان \(x\mid y\) فهناك أيضًا حركة فوز مباشرة. إذًا الجزء الحقيقي من المسألة يقع فقط في الشريط
$$x \lt y \lt 2x.$$
2) داخل هذا الشريط توجد حركة وحيدة.
عندما \(x \lt y \lt 2x\)، لا يمكن طرح إلا نسخة واحدة من الكومة الأصغر، فينتقل الوضع إلى
$$ (x,y)\to(y-x,x), $$
بعد إعادة الترتيب.
3) الحد الفاصل تحدده النسبة الذهبية.
اكتب \(y=x+d\). عندئذ تكون المواضع الخاسرة بالضبط هي
$$x \lt y \le \lfloor \varphi x\rfloor,$$
حيث
$$\varphi=\frac{1+\sqrt5}{2}.$$
وبشكل مكافئ، عند تثبيت \(x\) تكون الفروق المسموح بها
$$1\le d\le a_x,\qquad a_x=\left\lfloor\frac{x}{\varphi}\right\rfloor.$$
4) تحويل المطلوب إلى مجموع مزدوج.
إذًا
$$S(N)=\sum_{x=1}^{N}\sum_{d=1}^{\min(a_x,N-x)}(2x+d).$$
5) تقسيم إلى مقدمة وذيل.
لنعرّف
$$c=\left\lfloor\frac{N+1}{\varphi}\right\rfloor.$$
إذا كان \(x\le c\) فإن المجال الخاسر الكامل يبقى داخل الحد \(y\le N\). أما إذا كان \(x \gt c\) فيُقصّ المجال بواسطة \(N-x\).
6) ثلاث مجاميع من نوع Beatty.
نضع
$$G(n)=\sum_{k=1}^{n} a_k,\qquad P(n)=\sum_{k=1}^{n}k a_k,\qquad Q(n)=\sum_{k=1}^{n} a_k^2.$$
وعندها يكون جزء المقدمة
$$S_{\text{pref}}=\frac{4P(c)+Q(c)+G(c)}{2}.$$
7) لماذا نحصل على تراجع سريع.
إذا أخذنا
$$m=\left\lfloor\frac{n}{\varphi}\right\rfloor,$$
فإن هويات Beatty الكلاسيكية تسمح بإعادة كتابة \(G(n),P(n),Q(n)\) بدلالة القيم نفسها عند \(m\). وهكذا ينخفض الحجم في كل خطوة إلى نحو \(n/\varphi\).
8) الذيل يصبح مجموعات كثيرة حدود عادية.
عندما \(x \gt c\)، تصبح النهاية العليا للمجموع الداخلي هي \(N-x\)، ولذلك
$$\sum_{d=1}^{N-x}(2x+d)=2x(N-x)+\frac{(N-x)(N-x+1)}{2}.$$
ثم يختزل الذيل كله إلى تراكيب من \(\sum x\) و\(\sum x^2\).
9) مثال \(N=10\).
القيمة الصغيرة المستخدمة كفحص هي
$$S(10)=211.$$
1) وصف المواضع الخاسرة بواسطة \(a_x=\lfloor x/\varphi\rfloor\).
2) تقسيم المجموع عند \(c=\lfloor (N+1)/\varphi\rfloor\).
3) حساب جزء المقدمة بواسطة \(G,P,Q\).
4) حساب الذيل بصيغ مغلقة لـ \(\sum x\) و\(\sum x^2\).
5) تنفيذ الحساب نفسه بترديد \(7^{10}\).
عمق التراجع هو
$$O(\log N),$$
وفي كل مستوى لا نحتاج إلا إلى عدد ثابت من العمليات على أعداد كبيرة أو معيارية.
يتحقق البرنامج من
$$S(10)=211,\qquad S(10^4)=230312207313.$$
ولأجل
$$N=10^{16}$$
تكون النتيجة النهائية modulo \(7^{10}\) هي
$$54672965.$$