For each integer \(a\) with \(3 \le a \le 1000\), define \(r_n(a)\) to be the remainder when \((a-1)^n + (a+1)^n\) is divided by \(a^2\). The problem asks for the largest possible remainder \(r_{\max}(a)\) for each fixed \(a\), and then for the sum of these maxima over the whole range. The important point is that the exponent \(n\) is not fixed: we are free to choose the value of \(n\) that makes the remainder as large as possible.
A brute-force search over many exponents would miss the main structure. Once the expression is reduced modulo \(a^2\), almost the entire binomial expansion disappears, and the problem collapses to a short parity argument together with a small modular-arithmetic case split on whether \(a\) is odd or even.
The quantity to analyze is
$$r_n(a) \equiv (a-1)^n + (a+1)^n \pmod{a^2}.$$
The whole solution comes from understanding which terms of the two powers can survive modulo \(a^2\).
Expand both powers around \(\pm 1\):
$$ (a+1)^n = 1 + na + \binom{n}{2}a^2 + \cdots, $$
$$ (a-1)^n = (-1)^n + n(-1)^{n-1}a + \binom{n}{2}(-1)^{n-2}a^2 + \cdots. $$
Modulo \(a^2\), every term containing \(a^2\) or a higher power vanishes. Only the constant and linear terms matter, so
$$ (a+1)^n \equiv 1 + na \pmod{a^2}, \qquad (a-1)^n \equiv (-1)^n + n(-1)^{n-1}a \pmod{a^2}. $$
Adding them gives a complete reduction:
$$ r_n(a) \equiv \begin{cases} 2 \pmod{a^2}, & n \text{ even},\\ 2an \pmod{a^2}, & n \text{ odd}. \end{cases} $$
So the enormous-looking expression is really governed by only two pieces of data: the parity of \(n\), and, for odd \(n\), the residue of \(2n\) modulo \(a\).
When \(n\) is even, the remainder is always exactly \(2\). For \(a \ge 3\), the values obtained from odd exponents are much larger, because they are multiples of \(a\). In fact, once \(n\) is odd we can write
$$ r_n(a) = a \cdot (2n \bmod a), $$
where the factor \(2n \bmod a\) is taken in the range \(0,1,\dots,a-1\). Therefore maximizing the remainder is equivalent to maximizing the reachable residue \(2n \bmod a\) while keeping \(n\) odd.
Let \(n=2k+1\). Then
$$ 2n \equiv 4k+2 \pmod a. $$
As \(k\) increases by 1, this residue advances by \(4\) modulo \(a\). That turns the original problem into a very small orbit question in the ring \(\mathbb{Z}/a\mathbb{Z}\).
If \(a\) is odd, then \(\gcd(4,a)=1\). Repeatedly adding \(4\) modulo \(a\) visits every residue class, so among odd exponents we can reach every possible value from \(0\) to \(a-1\). In particular, the largest residue \(a-1\) is attainable, and therefore
$$ r_{\max}(a) = a(a-1) \qquad (a \text{ odd}). $$
If \(a\) is even, then \(2n\) is always even, so the residue \(a-1\) can never occur. The largest possible residue below \(a\) with the correct parity is \(a-2\). It is actually attained: choosing \(n=a-1\), which is odd, gives \(2n=2a-2 \equiv a-2 \pmod a\). Hence
$$ r_{\max}(a) = a(a-2) \qquad (a \text{ even}). $$
The case split can be written compactly as
$$ r_{\max}(a)= \begin{cases} a(a-2), & a \text{ even},\\ a(a-1), & a \text{ odd}. \end{cases} $$
This is exactly the formula used by the implementations. Once it has been proved, the original number-theory problem becomes a direct summation over \(a=3,4,\dots,1000\).
Take \(a=7\). For odd exponents, the coefficient \(2n \bmod 7\) runs through
$$ 2,6,3,0,4,1,5,\dots $$
so the largest reachable value is \(6\). Therefore \(r_{\max}(7)=7\cdot 6=42\).
Now take \(a=8\). For odd exponents, the coefficient \(2n \bmod 8\) runs through
$$ 2,6,2,6,\dots $$
Only even residues occur, and the best one is \(6=8-2\). Thus \(r_{\max}(8)=8\cdot 6=48\). These two examples show exactly why the final formula depends only on the parity of \(a\).
The C++, Python, and Java implementations do not search over exponents at all. They rely on the closed form above, loop over every integer \(a\) from \(3\) to \(1000\), determine whether \(a\) is odd or even, and add the corresponding contribution \(a(a-1)\) or \(a(a-2)\) to a running total.
This means the code is already working at the final mathematical level. All of the difficult reasoning is pushed into the derivation of \(r_{\max}(a)\); once that derivation is known, the implementation is just a short accumulation over 998 values of \(a\).
There is one pass through the integers \(a=3\) to \(1000\), and each iteration performs only a parity test, two small multiplications, and one addition. The running time is therefore \(O(1000)\), or more generally \(O(A)\) if the upper bound is \(A\). The memory usage is \(O(1)\), since the implementation stores only the running total and a few temporary integer values.
Für jede ganze Zahl \(a\) mit \(3 \le a \le 1000\) sei \(r_n(a)\) der Rest von \((a-1)^n + (a+1)^n\) bei Division durch \(a^2\). Gesucht ist für jedes feste \(a\) der größtmögliche Rest \(r_{\max}(a)\), und anschließend die Summe dieser Maximalwerte über alle \(a\) im Bereich. Der Exponent \(n\) darf dabei frei gewählt werden; gerade diese Freiheit macht die Struktur des Problems sichtbar.
Ein naiver Versuch, viele Exponenten auszuprobieren, wäre unnötig. Nach der Reduktion modulo \(a^2\) verschwinden fast alle Terme der Binomialentwicklung, und am Ende bleiben nur eine Paritätsunterscheidung für \(n\) und ein kleiner Fallunterschied zwischen geradem und ungeradem \(a\).
Zu untersuchen ist
$$r_n(a) \equiv (a-1)^n + (a+1)^n \pmod{a^2}.$$
Die zentrale Frage lautet: Welche Teile der beiden Potenzen überleben überhaupt modulo \(a^2\)?
Wir entwickeln beide Potenzen nach dem Binomialsatz:
$$ (a+1)^n = 1 + na + \binom{n}{2}a^2 + \cdots, $$
$$ (a-1)^n = (-1)^n + n(-1)^{n-1}a + \binom{n}{2}(-1)^{n-2}a^2 + \cdots. $$
Modulo \(a^2\) verschwinden alle Terme mit Faktor \(a^2\) oder höher. Damit bleiben nur Konstante und lineares Glied übrig:
$$ (a+1)^n \equiv 1 + na \pmod{a^2}, \qquad (a-1)^n \equiv (-1)^n + n(-1)^{n-1}a \pmod{a^2}. $$
Nach dem Addieren erhält man sofort
$$ r_n(a) \equiv \begin{cases} 2 \pmod{a^2}, & n \text{ gerade},\\ 2an \pmod{a^2}, & n \text{ ungerade}. \end{cases} $$
Damit hängt das Problem nur noch von zwei Dingen ab: von der Parität des Exponenten und, im ungeraden Fall, von der Restklasse von \(2n\) modulo \(a\).
Ist \(n\) gerade, dann ist der Rest immer exakt \(2\). Für \(a \ge 3\) liefern ungerade Exponenten deutlich größere Werte, weil dann der Rest ein Vielfaches von \(a\) ist. Für ungerades \(n\) kann man nämlich schreiben
$$ r_n(a) = a \cdot (2n \bmod a), $$
wobei \(2n \bmod a\) als Zahl zwischen \(0\) und \(a-1\) verstanden wird. Das Maximum des Restes ist also genau dann erreicht, wenn die größtmögliche erreichbare Restklasse von \(2n\) modulo \(a\) gefunden ist.
Setze \(n=2k+1\). Dann gilt
$$ 2n \equiv 4k+2 \pmod a. $$
Erhöht man \(k\) jeweils um 1, so wandert die Restklasse also in Schritten von \(4\) durch \(\mathbb{Z}/a\mathbb{Z}\). Genau hier entscheidet die Parität von \(a\).
Ist \(a\) ungerade, dann ist \(\gcd(4,a)=1\). Wiederholtes Addieren von \(4\) durchläuft daher alle Restklassen modulo \(a\). Insbesondere ist auch \(a-1\) erreichbar, also
$$ r_{\max}(a) = a(a-1) \qquad (a \text{ ungerade}). $$
Ist \(a\) gerade, dann ist \(2n\) immer gerade, und die Restklasse \(a-1\) ist unmöglich. Die größte zulässige Restklasse kleiner als \(a\) ist dann \(a-2\). Dass sie wirklich vorkommt, sieht man mit \(n=a-1\): Dieser Exponent ist ungerade und liefert \(2n=2a-2 \equiv a-2 \pmod a\). Somit folgt
$$ r_{\max}(a) = a(a-2) \qquad (a \text{ gerade}). $$
Damit steht die gesuchte Maximalformel vollständig fest:
$$ r_{\max}(a)= \begin{cases} a(a-2), & a \text{ gerade},\\ a(a-1), & a \text{ ungerade}. \end{cases} $$
Genau diese Fallunterscheidung verwenden die Implementierungen. Sobald sie bewiesen ist, bleibt nur noch eine einfache Summe über \(a=3,4,\dots,1000\).
Für \(a=7\) nehmen die Werte \(2n \bmod 7\) bei ungeradem \(n\) die Folge
$$ 2,6,3,0,4,1,5,\dots $$
an. Das Maximum ist \(6\), also gilt \(r_{\max}(7)=7\cdot 6=42\).
Für \(a=8\) erhält man bei ungeradem \(n\) die Folge
$$ 2,6,2,6,\dots $$
Es treten nur gerade Restklassen auf; die größte davon ist \(6=8-2\). Daher ist \(r_{\max}(8)=8\cdot 6=48\). Genau daran erkennt man den Unterschied zwischen geradem und ungeradem \(a\).
Die C++-, Python- und Java-Implementierungen durchsuchen keine Exponenten. Stattdessen nutzen sie unmittelbar die geschlossene Formel, laufen einmal über alle \(a\) von \(3\) bis \(1000\), testen die Parität von \(a\) und addieren je nach Fall entweder \(a(a-1)\) oder \(a(a-2)\) zu einer laufenden Summe.
Der eigentliche mathematische Aufwand steckt also vollständig in der Herleitung. Der Programmteil selbst ist bewusst kurz, weil die schwerste Arbeit bereits durch die modulare Analyse erledigt wurde.
Es gibt genau einen Durchlauf über die 998 Werte \(a=3,\dots,1000\). Jede Iteration benötigt nur einen Paritätstest, einige ganzzahlige Multiplikationen und eine Addition. Die Laufzeit ist daher \(O(1000)\), allgemeiner \(O(A)\) für eine obere Schranke \(A\). Der Speicherbedarf ist \(O(1)\), denn außer der aktuellen Summe und wenigen Hilfswerten wird nichts gespeichert.
\(3 \le a \le 1000\) aralığındaki her tam sayı için \(r_n(a)\), \((a-1)^n + (a+1)^n\) ifadesinin \(a^2\) ile bölümünden kalan olsun. İstenen şey, sabit bir \(a\) için alınabilecek en büyük kalan \(r_{\max}(a)\)'yı bulmak ve sonra bu maksimumları tüm \(a\) değerleri boyunca toplamaktır. Buradaki kritik nokta, üssün sabit olmamasıdır; en büyük kalanı verecek \(n\) serbestçe seçilebilir.
Yüzeyde bu, çok büyük üsler denenmesi gereken bir arama problemi gibi görünüyor. Oysa ifade \(a^2\) modunda sadeleştirildiğinde binom açılımının neredeyse tamamı yok olur. Geriye yalnızca \(n\)'nin tek-çift oluşu ve \(a\)'nın tek mi çift mi olduğu kalır.
İncelenecek büyüklük
$$r_n(a) \equiv (a-1)^n + (a+1)^n \pmod{a^2}$$
olduğuna göre, asıl soru şu hale gelir: bu toplamın hangi terimleri gerçekten \(a^2\) modunda hayatta kalır?
İki kuvveti binom açılımıyla yazalım:
$$ (a+1)^n = 1 + na + \binom{n}{2}a^2 + \cdots, $$
$$ (a-1)^n = (-1)^n + n(-1)^{n-1}a + \binom{n}{2}(-1)^{n-2}a^2 + \cdots. $$
\(a^2\) modunda, \(a^2\) veya daha yüksek kuvvet taşıyan tüm terimler sıfır olur. Bu yüzden yalnızca sabit ve doğrusal terimler kalır:
$$ (a+1)^n \equiv 1 + na \pmod{a^2}, \qquad (a-1)^n \equiv (-1)^n + n(-1)^{n-1}a \pmod{a^2}. $$
Toplayınca hemen şu iki durum elde edilir:
$$ r_n(a) \equiv \begin{cases} 2 \pmod{a^2}, & n \text{ çift},\\ 2an \pmod{a^2}, & n \text{ tek}. \end{cases} $$
Yani başlangıçtaki büyük ifade aslında yalnızca iki şeye bağlıdır: \(n\)'nin paritesi ve, \(n\) tekse, \(2n\)'nin \(a\) modundaki kalanı.
\(n\) çift olduğunda kalan her zaman tam olarak \(2\)'dir. Buna karşılık \(n\) tek olduğunda
$$ r_n(a) = a \cdot (2n \bmod a) $$
şeklinde yazabiliriz; burada \(2n \bmod a\), \(0\) ile \(a-1\) arasındaki temsilcidir. Dolayısıyla maksimum kalanı aramak, tek \(n\) değerleri arasında elde edilebilen en büyük \(2n \bmod a\) kalıntısını aramakla aynıdır. \(a \ge 3\) için bu değer, çift üslerin verdiği sabit \(2\)'den çok daha büyüktür.
\(n=2k+1\) yazalım. O zaman
$$ 2n \equiv 4k+2 \pmod a. $$
\(k\) bir arttığında kalıntı \(4\) kadar ilerler. Böylece sorun, \(\mathbb{Z}/a\mathbb{Z}\) içinde 4 adımlı bir yürüyüşe dönüşür.
\(a\) tekse \(\gcd(4,a)=1\) olur. Bu durumda \(4\) ile ardışık ilerlemek tüm kalıntı sınıflarını dolaşır; dolayısıyla \(a-1\) değeri de erişilebilir. Sonuç:
$$ r_{\max}(a) = a(a-1) \qquad (a \text{ tek}). $$
\(a\) çiftse \(2n\) her zaman çifttir, bu yüzden \(a-1\) gibi tek bir kalıntı asla görülemez. \(a\)'dan küçük en büyük uygun değer \(a-2\)'dir. Bunun gerçekten elde edildiğini görmek için \(n=a-1\) seçmek yeterlidir; bu üs tektir ve
$$ 2n = 2a-2 \equiv a-2 \pmod a $$
verir. Böylece
$$ r_{\max}(a) = a(a-2) \qquad (a \text{ çift}) $$
olur.
İki durum birlikte yazılırsa
$$ r_{\max}(a)= \begin{cases} a(a-2), & a \text{ çift},\\ a(a-1), & a \text{ tek}. \end{cases} $$
Uygulamaların kullandığı tam formül budur. Bundan sonra geriye yalnızca \(a=3,4,\dots,1000\) için bu değerleri toplamak kalır.
\(a=7\) için, tek üslerde \(2n \bmod 7\) dizisi
$$ 2,6,3,0,4,1,5,\dots $$
şeklinde gider. En büyük erişilebilir değer \(6\) olduğu için \(r_{\max}(7)=7\cdot 6=42\) olur.
\(a=8\) için ise tek üslerde
$$ 2,6,2,6,\dots $$
elde edilir. Yalnızca çift kalıntılar görünür ve bunların en büyüğü \(6=8-2\)'dir. Dolayısıyla \(r_{\max}(8)=8\cdot 6=48\). Bu iki örnek, sonucun neden doğrudan \(a\)'nın paritesine bağlı olduğunu açıkça gösterir.
C++, Python ve Java uygulamaları üs taraması yapmaz. Bunun yerine yukarıdaki kapalı formülü doğrudan kullanır, \(a=3\) ile \(a=1000\) arasındaki bütün değerleri tek bir döngüyle gezer, \(a\)'nın tek mi çift mi olduğuna bakar ve uygun terimi \(a(a-1)\) ya da \(a(a-2)\) olarak toplamın içine ekler.
Böylece kod, matematiksel indirgemeden sonra kalan son aşamayı uygular. Zor kısmı üstel hesaplama değil, formülün neden doğru olduğunu kanıtlamaktır.
Algoritma 998 adet \(a\) değeri üzerinden tek geçiş yapar. Her adımda yalnızca bir parite kontrolü, birkaç tam sayı çarpımı ve bir toplama işlemi vardır. Bu nedenle çalışma süresi \(O(1000)\), daha genel bir üst sınır \(A\) için \(O(A)\)'dır. Ek bellek kullanımı \(O(1)\)'dir; sadece kümülatif toplam ve birkaç geçici tam sayı tutulur.
Para cada entero \(a\) con \(3 \le a \le 1000\), definimos \(r_n(a)\) como el resto de dividir \((a-1)^n + (a+1)^n\) entre \(a^2\). La tarea consiste en hallar, para cada valor fijo de \(a\), el mayor resto posible \(r_{\max}(a)\), y luego sumar esos máximos en todo el intervalo. El punto clave es que el exponente \(n\) no está fijado de antemano; podemos elegirlo de la manera que más convenga.
A primera vista parece un problema de probar muchos exponentes. Sin embargo, al reducir la expresión módulo \(a^2\), casi toda la expansión binomial desaparece. El resultado final depende solo de la paridad de \(n\) y de si \(a\) es par o impar.
La cantidad que hay que estudiar es
$$r_n(a) \equiv (a-1)^n + (a+1)^n \pmod{a^2}.$$
La pregunta central es cuáles términos sobreviven realmente al trabajar módulo \(a^2\).
Desarrollamos ambas potencias:
$$ (a+1)^n = 1 + na + \binom{n}{2}a^2 + \cdots, $$
$$ (a-1)^n = (-1)^n + n(-1)^{n-1}a + \binom{n}{2}(-1)^{n-2}a^2 + \cdots. $$
Módulo \(a^2\), todo término con factor \(a^2\) o superior se anula. Solo importan la constante y el término lineal:
$$ (a+1)^n \equiv 1 + na \pmod{a^2}, \qquad (a-1)^n \equiv (-1)^n + n(-1)^{n-1}a \pmod{a^2}. $$
Al sumar, obtenemos una descripción completa:
$$ r_n(a) \equiv \begin{cases} 2 \pmod{a^2}, & n \text{ par},\\ 2an \pmod{a^2}, & n \text{ impar}. \end{cases} $$
Así, la expresión original queda reducida a dos datos: la paridad de \(n\) y, en el caso impar, la clase residual de \(2n\) módulo \(a\).
Si \(n\) es par, el resto siempre vale exactamente \(2\). En cambio, si \(n\) es impar, podemos escribir
$$ r_n(a) = a \cdot (2n \bmod a), $$
donde \(2n \bmod a\) se toma entre \(0\) y \(a-1\). Por lo tanto, maximizar el resto equivale a maximizar la mayor clase residual alcanzable de \(2n\) módulo \(a\) bajo la restricción de que \(n\) sea impar. Para \(a \ge 3\), esos valores superan claramente al resto fijo \(2\) del caso par.
Escribamos \(n=2k+1\). Entonces
$$ 2n \equiv 4k+2 \pmod a. $$
Cada vez que \(k\) aumenta en 1, el residuo avanza en \(4\) módulo \(a\). Toda la dificultad se convierte así en entender esta órbita aritmética.
Si \(a\) es impar, \(\gcd(4,a)=1\). Por eso, sumar \(4\) repetidamente recorre todas las clases residuales módulo \(a\). En particular, se alcanza el mayor residuo posible, \(a-1\), y por tanto
$$ r_{\max}(a) = a(a-1) \qquad (a \text{ impar}). $$
Si \(a\) es par, entonces \(2n\) siempre es par y el residuo \(a-1\) nunca puede aparecer. El mejor valor disponible por debajo de \(a\) es \(a-2\). Además sí se alcanza: basta tomar \(n=a-1\), que es impar, y entonces \(2n=2a-2 \equiv a-2 \pmod a\). En consecuencia,
$$ r_{\max}(a) = a(a-2) \qquad (a \text{ par}). $$
La respuesta para un \(a\) fijo queda resumida en
$$ r_{\max}(a)= \begin{cases} a(a-2), & a \text{ par},\\ a(a-1), & a \text{ impar}. \end{cases} $$
Esta es exactamente la fórmula que usan las implementaciones. Después de demostrarla, el problema original se reduce a una suma directa sobre \(a=3,4,\dots,1000\).
Para \(a=7\), los valores de \(2n \bmod 7\) cuando \(n\) es impar son
$$ 2,6,3,0,4,1,5,\dots $$
El máximo alcanzable es \(6\), así que \(r_{\max}(7)=7\cdot 6=42\).
Para \(a=8\), los valores correspondientes son
$$ 2,6,2,6,\dots $$
Solo aparecen residuos pares, y el mayor es \(6=8-2\). Entonces \(r_{\max}(8)=8\cdot 6=48\). Los dos ejemplos muestran con claridad por qué el resultado depende únicamente de la paridad de \(a\).
Las implementaciones en C++, Python y Java no prueban exponentes uno por uno. Usan directamente la fórmula cerrada, recorren todos los valores de \(a\) entre \(3\) y \(1000\), comprueban si \(a\) es par o impar, y añaden a un acumulador el término correspondiente \(a(a-2)\) o \(a(a-1)\).
Eso significa que el trabajo difícil ya fue absorbido por la demostración matemática. Una vez obtenido \(r_{\max}(a)\), el programa es solo una suma lineal muy corta.
Se realiza una única pasada sobre 998 valores de \(a\). Cada iteración requiere una comprobación de paridad, unas pocas multiplicaciones enteras y una suma. Por tanto, el tiempo de ejecución es \(O(1000)\), o en forma general \(O(A)\) si el límite superior es \(A\). El uso de memoria es \(O(1)\), porque solo se mantiene el total acumulado y unas pocas variables enteras temporales.
对每个满足 \(3 \le a \le 1000\) 的整数 \(a\)，记 \(r_n(a)\) 为 \((a-1)^n + (a+1)^n\) 除以 \(a^2\) 的余数。题目要求先对每个固定的 \(a\) 求出可能出现的最大余数 \(r_{\max}(a)\)，再把这些最大值在整个区间上求和。关键在于指数 \(n\) 不是固定参数，而是可以自由选择，因此问题的本质并不是计算某个具体幂，而是分析哪些余数模式真正可能出现。
如果直接对很多 \(n\) 做试算，看起来会像一个暴力枚举问题。但一旦把表达式放到模 \(a^2\) 的框架里，二项式展开中的绝大多数项都会消失，问题会迅速收缩成一个非常小的同余分析：只需要区分 \(n\) 的奇偶性，以及 \(a\) 的奇偶性。
需要研究的对象是
$$r_n(a) \equiv (a-1)^n + (a+1)^n \pmod{a^2}.$$
因此核心问题变成：把两个幂展开以后，哪些项在模 \(a^2\) 下还能留下来？
先分别展开两项：
$$ (a+1)^n = 1 + na + \binom{n}{2}a^2 + \cdots, $$
$$ (a-1)^n = (-1)^n + n(-1)^{n-1}a + \binom{n}{2}(-1)^{n-2}a^2 + \cdots. $$
在模 \(a^2\) 的意义下，所有含有 \(a^2\) 或更高次幂的项都会变成 0，所以真正保留下来的只有常数项和一次项：
$$ (a+1)^n \equiv 1 + na \pmod{a^2}, \qquad (a-1)^n \equiv (-1)^n + n(-1)^{n-1}a \pmod{a^2}. $$
把它们相加，立刻得到完整的分类：
$$ r_n(a) \equiv \begin{cases} 2 \pmod{a^2}, & n \text{ 为偶数},\\ 2an \pmod{a^2}, & n \text{ 为奇数}. \end{cases} $$
这一步非常关键，因为它说明原式虽然长得像高次幂问题，但在模 \(a^2\) 下，真正决定结果的只剩下两件事：指数 \(n\) 的奇偶性，以及在奇数指数情形下的 \(2n \bmod a\)。
当 \(n\) 为偶数时，余数恒等于 \(2\)。而当 \(n\) 为奇数时，可以把余数写成
$$ r_n(a) = a \cdot (2n \bmod a), $$
这里 \(2n \bmod a\) 取的是 \(0,1,\dots,a-1\) 中的标准代表元。于是问题就变成：在 \(n\) 必须为奇数的条件下，\(2n \bmod a\) 能取得多大的值？只要这个系数比 1 大，最终余数就已经远远超过偶数指数所给出的常数 2 了，所以真正的最大值一定来自奇数指数。
把奇数指数写成 \(n=2k+1\)。那么
$$ 2n \equiv 4k+2 \pmod a. $$
也就是说，当 \(k\) 每增加 1，系数就在模 \(a\) 的意义下向前移动 4。这把原问题化成了一个非常具体的轨道问题：从 2 出发，不断加 4，最终会访问哪些剩余类？
如果 \(a\) 是奇数，那么 \(\gcd(4,a)=1\)。这意味着不断加 4 会遍历模 \(a\) 的全部剩余类，因此最大的剩余类 \(a-1\) 一定能被访问到。于是
$$ r_{\max}(a) = a(a-1) \qquad (a \text{ 为奇数}). $$
如果 \(a\) 是偶数，那么 \(2n\) 永远是偶数，因此 \(a-1\) 这种奇数剩余类根本不可能出现。此时小于 \(a\) 的最大可行值只能是 \(a-2\)。而且它确实可以达到：取 \(n=a-1\)，这是一个奇数，并且
$$ 2n = 2a-2 \equiv a-2 \pmod a. $$
因此有
$$ r_{\max}(a) = a(a-2) \qquad (a \text{ 为偶数}). $$
把两种情形合并起来，得到整个问题最核心的公式：
$$ r_{\max}(a)= \begin{cases} a(a-2), & a \text{ 为偶数},\\ a(a-1), & a \text{ 为奇数}. \end{cases} $$
实现代码正是按照这个公式逐项求和的。也就是说，真正困难的部分不是程序本身，而是证明为什么原来那个幂表达式会简化成这样一个只看奇偶性的闭式。
先看 \(a=7\)。当 \(n\) 取奇数时，\(2n \bmod 7\) 形成的序列是
$$ 2,6,3,0,4,1,5,\dots $$
可达到的最大值是 6，所以最大余数为 \(7 \cdot 6 = 42\)。
再看 \(a=8\)。这时对应序列变成
$$ 2,6,2,6,\dots $$
只会出现偶数剩余类，最大值是 \(6=8-2\)，所以最大余数为 \(8 \cdot 6 = 48\)。这两个例子刚好展示了为什么最后答案只取决于 \(a\) 的奇偶性，而不需要对指数进行漫长搜索。
C++、Python 和 Java 三个实现都没有去枚举指数 \(n\)。它们直接使用上面的闭式，对 \(a=3\) 到 \(1000\) 做一次线性扫描：如果 \(a\) 是奇数，就把 \(a(a-1)\) 加入总和；如果 \(a\) 是偶数，就把 \(a(a-2)\) 加入总和。
因此，代码层面几乎没有复杂结构。真正决定解法质量的是前面的数学压缩：先把高次幂问题缩成一个模运算问题，再把模运算问题缩成一个简单的奇偶分类。
算法只遍历 998 个整数 \(a\)，每一步都只做常数次操作：一次奇偶判断、几次整数乘法和一次累加。因此时间复杂度是 \(O(1000)\)，更一般地说，对上界 \(A\) 的复杂度是 \(O(A)\)。空间复杂度是 \(O(1)\)，因为实现只保存当前累计和以及少量临时整数。
Для каждого целого \(a\) из диапазона \(3 \le a \le 1000\) обозначим через \(r_n(a)\) остаток от деления \((a-1)^n + (a+1)^n\) на \(a^2\). Нужно для каждого фиксированного \(a\) найти наибольший возможный остаток \(r_{\max}(a)\), а затем просуммировать эти максимумы по всем значениям \(a\). Важная особенность задачи состоит в том, что показатель \(n\) можно выбирать свободно, а значит нужно понять не отдельное значение выражения, а всю структуру возможных остатков.
На первый взгляд здесь напрашивается перебор многих степеней. Но после перехода к арифметике по модулю \(a^2\) почти вся биномиальная формула исчезает, и задача сводится к очень короткому рассуждению о чётности и достижимых остатках по модулю \(a\).
Исследовать нужно выражение
$$r_n(a) \equiv (a-1)^n + (a+1)^n \pmod{a^2}.$$
Поэтому главный вопрос таков: какие члены разложения вообще переживают редукцию по модулю \(a^2\)?
Разложим обе степени:
$$ (a+1)^n = 1 + na + \binom{n}{2}a^2 + \cdots, $$
$$ (a-1)^n = (-1)^n + n(-1)^{n-1}a + \binom{n}{2}(-1)^{n-2}a^2 + \cdots. $$
По модулю \(a^2\) все слагаемые с \(a^2\) и более высокими степенями исчезают. Остаются только константа и линейный член:
$$ (a+1)^n \equiv 1 + na \pmod{a^2}, \qquad (a-1)^n \equiv (-1)^n + n(-1)^{n-1}a \pmod{a^2}. $$
После сложения получаем полное описание:
$$ r_n(a) \equiv \begin{cases} 2 \pmod{a^2}, & n \text{ чётное},\\ 2an \pmod{a^2}, & n \text{ нечётное}. \end{cases} $$
Итак, исходная задача зависит лишь от двух вещей: от чётности \(n\) и, в нечётном случае, от остатка \(2n\) по модулю \(a\).
Если \(n\) чётно, остаток всегда равен ровно \(2\). Если же \(n\) нечётно, то остаток можно записать так:
$$ r_n(a) = a \cdot (2n \bmod a), $$
где \(2n \bmod a\) понимается как число от \(0\) до \(a-1\). Значит, максимизация остатка эквивалентна поиску наибольшего достижимого значения \(2n \bmod a\) при условии, что \(n\) нечётно. Для \(a \ge 3\) такие значения заведомо превосходят постоянный остаток 2 из чётного случая.
Положим \(n=2k+1\). Тогда
$$ 2n \equiv 4k+2 \pmod a. $$
При увеличении \(k\) на 1 соответствующий остаток сдвигается на \(4\) по модулю \(a\). Тем самым задача превращается в вопрос о траектории, получаемой многократным прибавлением 4 в \(\mathbb{Z}/a\mathbb{Z}\).
Если \(a\) нечётно, то \(\gcd(4,a)=1\). Поэтому последовательные прибавления 4 обходят все классы вычетов по модулю \(a\). В частности, достижим максимальный вычет \(a-1\), и значит
$$ r_{\max}(a) = a(a-1) \qquad (a \text{ нечётное}). $$
Если \(a\) чётно, то \(2n\) всегда чётно, а значит вычет \(a-1\) невозможен. Наибольший допустимый вычет меньше \(a\) тогда равен \(a-2\). Он действительно достигается: достаточно взять \(n=a-1\), это нечётное число, и
$$ 2n = 2a-2 \equiv a-2 \pmod a. $$
Следовательно,
$$ r_{\max}(a) = a(a-2) \qquad (a \text{ чётное}). $$
Обе ситуации объединяются в одну компактную формулу:
$$ r_{\max}(a)= \begin{cases} a(a-2), & a \text{ чётное},\\ a(a-1), & a \text{ нечётное}. \end{cases} $$
Именно эту формулу используют реализации. После её доказательства исходная задача сводится к обычной сумме по \(a=3,4,\dots,1000\).
Для \(a=7\) последовательность \(2n \bmod 7\) при нечётных \(n\) имеет вид
$$ 2,6,3,0,4,1,5,\dots $$
Максимально достижимое значение равно 6, поэтому \(r_{\max}(7)=7\cdot 6=42\).
Для \(a=8\) получаем
$$ 2,6,2,6,\dots $$
Появляются только чётные вычеты, и лучший из них равен \(6=8-2\). Значит, \(r_{\max}(8)=8\cdot 6=48\). Эти два примера наглядно показывают, почему окончательная формула зависит только от чётности \(a\).
Реализации на C++, Python и Java вообще не перебирают степени \(n\). Они сразу используют доказанную формулу, проходят по всем значениям \(a\) от \(3\) до \(1000\), определяют чётность \(a\) и добавляют к сумме либо \(a(a-2)\), либо \(a(a-1)\).
Тем самым программная часть остаётся очень короткой. Вся содержательная сложность решения сосредоточена в математическом выводе, а не в самой реализации.
Алгоритм делает один проход по 998 значениям \(a\). На каждом шаге выполняются только проверка чётности, несколько целочисленных умножений и одно сложение. Поэтому время работы равно \(O(1000)\), а в общем виде \(O(A)\) для верхней границы \(A\). Память равна \(O(1)\), потому что хранится только текущая сумма и несколько временных целых переменных.
لكل عدد صحيح \(a\) يحقق \(3 \le a \le 1000\)، نعرّف \(r_n(a)\) بأنه باقي قسمة \((a-1)^n + (a+1)^n\) على \(a^2\). المطلوب هو إيجاد أكبر باقي ممكن \(r_{\max}(a)\) لكل قيمة ثابتة من \(a\)، ثم جمع هذه القيم العظمى على كامل المجال. الفكرة الجوهرية هي أن الأس \(n\) ليس ثابتًا؛ بل يمكن اختياره بحرية، ولذلك يجب فهم البنية العامة للبواقي الممكنة بدلًا من تجربة أسس كثيرة بشكل أعمى.
لو بدا الأمر من الوهلة الأولى مسألة بحث بالقوة الغاشمة، فإن التحليل في الحسابيات المعيارية modulo \(a^2\) يغيّر الصورة تمامًا. بعد التوسيع ذي الحدين تختفي معظم الحدود، ولا يبقى في النهاية إلا اعتماد بسيط على زوجية أو فردية \(n\)، ثم انقسام آخر بحسب كون \(a\) زوجيًا أو فرديًا.
الكمية التي نريد تحليلها هي
$$r_n(a) \equiv (a-1)^n + (a+1)^n \pmod{a^2}.$$
إذًا السؤال المركزي هو: أي حدود من التوسيع تبقى فعلًا بعد الاختزال modulo \(a^2\)؟
نكتب التوسعين:
$$ (a+1)^n = 1 + na + \binom{n}{2}a^2 + \cdots, $$
$$ (a-1)^n = (-1)^n + n(-1)^{n-1}a + \binom{n}{2}(-1)^{n-2}a^2 + \cdots. $$
عند العمل modulo \(a^2\)، فإن كل حد يحتوي على \(a^2\) أو قوة أعلى من \(a\) يختفي. لذلك لا يبقى إلا الحد الثابت والحد الخطي:
$$ (a+1)^n \equiv 1 + na \pmod{a^2}, \qquad (a-1)^n \equiv (-1)^n + n(-1)^{n-1}a \pmod{a^2}. $$
وبجمعهما نحصل على الوصف الكامل:
$$ r_n(a) \equiv \begin{cases} 2 \pmod{a^2}, & n \equiv 0 \pmod 2,\\ 2an \pmod{a^2}, & n \equiv 1 \pmod 2. \end{cases} $$
إذن التعبير الأصلي، رغم شكله الكبير، تحدده في الحقيقة معلومتان فقط: زوجية \(n\) أو فرديته، ثم قيمة \(2n \bmod a\) عندما يكون \(n\) فرديًا.
إذا كان \(n\) زوجيًا فإن الباقي يساوي دائمًا \(2\). أما إذا كان \(n\) فرديًا، فيمكن كتابة الباقي على الصورة
$$ r_n(a) = a \cdot (2n \bmod a), $$
حيث يؤخذ \(2n \bmod a\) ممثلًا بين \(0\) و\(a-1\). وهكذا تصبح مهمة تعظيم الباقي مساوية تمامًا لتعظيم أكبر قيمة ممكنة للباقي \(2n \bmod a\) مع الشرط أن يكون \(n\) فرديًا. وبالنسبة إلى \(a \ge 3\)، تكون هذه القيم أكبر بكثير من الباقي الثابت \(2\) القادم من الحالة الزوجية.
لنكتب \(n=2k+1\). عندئذٍ
$$ 2n \equiv 4k+2 \pmod a. $$
كلما زادت \(k\) بمقدار 1، تحرك هذا الباقي بمقدار \(4\) modulo \(a\). وبذلك تتحول المسألة كلها إلى دراسة المدار الناتج عن الإضافة المتكررة للعدد 4 في \(\mathbb{Z}/a\mathbb{Z}\).
إذا كان \(a\) فرديًا، فإن \(\gcd(4,a)=1\). لهذا السبب، فإن الإضافة المتكررة للعدد 4 تمر على جميع أصناف البواقي modulo \(a\). وبالتالي يمكن الوصول إلى أكبر باقٍ ممكن وهو \(a-1\)، ومن ثم
$$ r_{\max}(a) = a(a-1) \qquad (a \equiv 1 \pmod 2). $$
أما إذا كان \(a\) زوجيًا، فإن \(2n\) يكون دائمًا عددًا زوجيًا، ولذلك لا يمكن أبدًا الوصول إلى الباقي \(a-1\). أفضل قيمة ممكنة أصغر من \(a\) هي إذًا \(a-2\)، وهي تتحقق فعلًا باختيار \(n=a-1\)، وهو عدد فردي، فنحصل على
$$ 2n = 2a-2 \equiv a-2 \pmod a. $$
وعليه
$$ r_{\max}(a) = a(a-2) \qquad (a \equiv 0 \pmod 2). $$
يمكن جمع الحالتين في صيغة واحدة:
$$ r_{\max}(a)= \begin{cases} a(a-2), & a \equiv 0 \pmod 2,\\ a(a-1), & a \equiv 1 \pmod 2. \end{cases} $$
هذه هي الصيغة التي تعتمدها التطبيقات مباشرة. وبعد الوصول إليها، تختفي صعوبة المسألة الأصلية ويتبقى مجرد جمع هذه القيم من \(a=3\) حتى \(a=1000\).
إذا أخذنا \(a=7\)، فإن القيم التي يأخذها \(2n \bmod 7\) عندما يكون \(n\) فرديًا هي
$$ 2,6,3,0,4,1,5,\dots $$
وأكبر قيمة ممكنة هي \(6\)، ولذلك يكون \(r_{\max}(7)=7\cdot 6=42\).
أما عند \(a=8\)، فإن السلسلة تصبح
$$ 2,6,2,6,\dots $$
ولا تظهر إلا بواقي زوجية، وأكبرها هو \(6=8-2\). لذلك نحصل على \(r_{\max}(8)=8\cdot 6=48\). هذان المثالان يوضحان مباشرة لماذا تعتمد الإجابة النهائية فقط على زوجية \(a\) أو فرديته.
التطبيقات في C++ وPython وJava لا تجرّب الأسس \(n\) واحدًا واحدًا. بدلًا من ذلك تستخدم الصيغة المغلقة مباشرة، وتنفذ مرورًا خطيًا على القيم \(a=3,4,\dots,1000\). إذا كانت \(a\) فردية تضيف \(a(a-1)\)، وإذا كانت زوجية تضيف \(a(a-2)\)، ثم تتابع جمع النتيجة.
هذا يعني أن الجزء البرمجي نفسه بسيط جدًا. الصعوبة الحقيقية موجودة في البرهان الرياضي الذي يحول مسألة قوى كبيرة إلى اختبار بسيط لزوجية \(a\).
توجد دورة واحدة فقط على 998 قيمة من \(a\). في كل خطوة تُجرى مقارنة بسيطة للزوجية، مع عدد ثابت من عمليات الضرب والجمع الصحيحة. لذلك فإن زمن التنفيذ هو \(O(1000)\)، وبصورة عامة \(O(A)\) إذا كانت النهاية العليا هي \(A\). أما الذاكرة المستعملة فهي \(O(1)\)، لأن التطبيق يحتفظ فقط بالمجموع الجاري وبعض القيم الصحيحة المؤقتة.