For an exclusive upper bound \(N\), we want the sum of all positive integers \(n \lt N\) such that \(3 \mid n\) or \(5 \mid n\). The only subtlety is overlap: numbers divisible by both 3 and 5 must be counted once, not twice.
The implementations do not scan every integer below \(N\). They exploit two concrete facts specific to this problem: multiples of a fixed divisor form an arithmetic progression, and the common multiples of 3 and 5 are exactly the multiples of 15.
For each positive divisor \(m\), define
$$A_m(N)=\{x\in\mathbb{N}: x \lt N,\; m \mid x\}.$$
Then the target sum is
$$\sum_{x \in A_3(N)\cup A_5(N)} x.$$
The two relevant sets are \(A_3(N)\) and \(A_5(N)\). Their intersection is not mysterious: a number belongs to both exactly when it is divisible by \(\operatorname{lcm}(3,5)=15\). Hence
$$A_3(N)\cap A_5(N)=A_{15}(N).$$
This is the core invariant behind the whole solution. Everything reduces to summing three structured sets: multiples of 3, multiples of 5, and the overlap at 15.
Fix a divisor \(m\). The admissible multiples below \(N\) are
$$m,\,2m,\,3m,\,\dots,\,q_m m,$$
where
$$q_m=\left\lfloor \frac{N-1}{m}\right\rfloor.$$
The use of \(N-1\) is important because the bound is strict. Equivalently, \(q_m\) is the unique integer satisfying
$$q_m m \lt N \le (q_m+1)m.$$
So the implementations never need to test each candidate individually; they only need the count \(q_m\).
Once \(q_m\) is known, the corresponding sum is
$$S_m(N)=\sum_{x\in A_m(N)} x = m(1+2+\cdots+q_m).$$
Using the triangular-number identity
$$1+2+\cdots+q_m=\frac{q_m(q_m+1)}{2},$$
we obtain the closed form
$$S_m(N)=m\cdot \frac{q_m(q_m+1)}{2}.$$
For this problem there is no recurrence to maintain and no dynamic state to update. The arithmetic progression collapses directly into a constant-time formula.
If we add \(S_3(N)\) and \(S_5(N)\), every multiple of 15 appears twice. Inclusion-exclusion removes exactly that extra copy:
$$\sum_{x \in A_3(N)\cup A_5(N)} x = S_3(N)+S_5(N)-S_{15}(N).$$
Substituting the closed forms gives
$$\boxed{\sum_{x \in A_3(N)\cup A_5(N)} x= 3\cdot\frac{q_3(q_3+1)}{2} +5\cdot\frac{q_5(q_5+1)}{2} -15\cdot\frac{q_{15}(q_{15}+1)}{2}},$$
with
$$q_3=\left\lfloor\frac{N-1}{3}\right\rfloor,\qquad q_5=\left\lfloor\frac{N-1}{5}\right\rfloor,\qquad q_{15}=\left\lfloor\frac{N-1}{15}\right\rfloor.$$
The relevant numbers are \(3,5,6,9,10,12,15\), whose direct sum is 60. The formula reaches the same result without listing them one by one:
$$q_3=\left\lfloor\frac{15}{3}\right\rfloor=5,\qquad S_3=3\cdot\frac{5\cdot6}{2}=45,$$
$$q_5=\left\lfloor\frac{15}{5}\right\rfloor=3,\qquad S_5=5\cdot\frac{3\cdot4}{2}=30,$$
$$q_{15}=\left\lfloor\frac{15}{15}\right\rfloor=1,\qquad S_{15}=15\cdot\frac{1\cdot2}{2}=15.$$
Therefore
$$45+30-15=60.$$
The subtraction of \(S_{15}\) is exactly what prevents the value 15 from being counted twice.
The C++, Python, and Java implementations all follow the same mathematical pipeline. First they treat the zero limit as a degenerate case before forming the expression \(N-1\); this keeps the counting step well-defined even when there are no positive integers below the bound.
Next they evaluate the count of admissible multiples for 3, 5, and 15 using integer division. For each of those three divisors, the implementation applies the closed form \(m\cdot q_m(q_m+1)/2\), so the sum is computed entirely with integer arithmetic and without any loop over \(1,2,\dots,N-1\).
Finally, the implementation combines the three partial sums as \(S_3+S_5-S_{15}\). All three versions also verify the standard checkpoint \(N=10 \mapsto 23\), and the standard Project Euler instance uses \(N=1000\).
The running time is \(O(1)\): the algorithm performs a fixed number of integer divisions, multiplications, additions, and one subtraction. The memory usage is also \(O(1)\).
A naive approach would inspect every integer below \(N\) and test divisibility by 3 or 5, which costs \(O(N)\) time. The closed form removes that dependence on the size of the bound.
Für eine exklusive obere Schranke \(N\) ist die Summe aller positiven ganzen Zahlen \(n \lt N\) gesucht, für die \(3 \mid n\) oder \(5 \mid n\) gilt. Die einzige heikle Stelle ist die Überlappung: Zahlen, die durch 3 und 5 zugleich teilbar sind, dürfen nicht doppelt gezählt werden.
Die Implementierungen prüfen deshalb nicht jede Zahl unterhalb von \(N\). Sie nutzen zwei ganz konkrete Strukturen dieser Aufgabe: Die Vielfachen eines festen Teilers bilden eine arithmetische Folge, und die gemeinsamen Vielfachen von 3 und 5 sind genau die Vielfachen von 15.
Für jeden positiven Teiler \(m\) definieren wir
$$A_m(N)=\{x\in\mathbb{N}: x \lt N,\; m \mid x\}.$$
Gesucht ist also
$$\sum_{x \in A_3(N)\cup A_5(N)} x.$$
Die beiden zentralen Mengen sind \(A_3(N)\) und \(A_5(N)\). Ihr Schnitt ist eindeutig bestimmt: Eine Zahl liegt genau dann in beiden Mengen, wenn sie durch \(\operatorname{lcm}(3,5)=15\) teilbar ist. Also gilt
$$A_3(N)\cap A_5(N)=A_{15}(N).$$
Das ist die tragende Invariante der gesamten Lösung. Am Ende müssen nur drei strukturierte Summen korrekt kombiniert werden: die Vielfachen von 3, die Vielfachen von 5 und die Überlappung bei 15.
Fixiere einen Teiler \(m\). Dann sind die zulässigen Vielfachen unterhalb von \(N\)
$$m,\,2m,\,3m,\,\dots,\,q_m m,$$
wobei
$$q_m=\left\lfloor \frac{N-1}{m}\right\rfloor.$$
Dass hier \(N-1\) erscheint, ist entscheidend, denn die Schranke ist strikt. Äquivalent ist \(q_m\) durch
$$q_m m \lt N \le (q_m+1)m$$
charakterisiert. Deshalb müssen die Implementierungen nicht jede Kandidatenzahl testen; sie brauchen nur die Anzahl \(q_m\).
Ist \(q_m\) bekannt, dann lautet die entsprechende Summe
$$S_m(N)=\sum_{x\in A_m(N)} x = m(1+2+\cdots+q_m).$$
Mit der Dreieckszahl-Identität
$$1+2+\cdots+q_m=\frac{q_m(q_m+1)}{2}$$
erhält man sofort
$$S_m(N)=m\cdot \frac{q_m(q_m+1)}{2}.$$
Für dieses Problem gibt es also weder eine Rekursion noch einen dynamischen Zustandsraum. Die arithmetische Folge kollabiert direkt zu einer \(O(1)\)-Formel.
Wenn man \(S_3(N)\) und \(S_5(N)\) addiert, wird jedes Vielfache von 15 doppelt erfasst. Genau dieses eine Extraexemplar entfernt Inklusion-Exklusion:
$$\sum_{x \in A_3(N)\cup A_5(N)} x = S_3(N)+S_5(N)-S_{15}(N).$$
Nach Einsetzen der geschlossenen Formen folgt
$$\boxed{\sum_{x \in A_3(N)\cup A_5(N)} x= 3\cdot\frac{q_3(q_3+1)}{2} +5\cdot\frac{q_5(q_5+1)}{2} -15\cdot\frac{q_{15}(q_{15}+1)}{2}},$$
mit
$$q_3=\left\lfloor\frac{N-1}{3}\right\rfloor,\qquad q_5=\left\lfloor\frac{N-1}{5}\right\rfloor,\qquad q_{15}=\left\lfloor\frac{N-1}{15}\right\rfloor.$$
Die relevanten Zahlen sind \(3,5,6,9,10,12,15\); direkt addiert ergibt das 60. Die Formel liefert denselben Wert, ohne die Liste explizit durchzugehen:
$$q_3=\left\lfloor\frac{15}{3}\right\rfloor=5,\qquad S_3=3\cdot\frac{5\cdot6}{2}=45,$$
$$q_5=\left\lfloor\frac{15}{5}\right\rfloor=3,\qquad S_5=5\cdot\frac{3\cdot4}{2}=30,$$
$$q_{15}=\left\lfloor\frac{15}{15}\right\rfloor=1,\qquad S_{15}=15\cdot\frac{1\cdot2}{2}=15.$$
Daher gilt
$$45+30-15=60.$$
Die Subtraktion von \(S_{15}\) ist genau der Schritt, der verhindert, dass der Wert 15 doppelt eingeht.
Die C++-, Python- und Java-Implementierungen folgen alle derselben mathematischen Abfolge. Zuerst behandeln sie den Grenzfall \(N=0\), bevor der Ausdruck \(N-1\) gebildet wird; so bleibt die Zählung auch dann sauber definiert, wenn unterhalb der Schranke keine positiven Zahlen existieren.
Danach berechnen sie für die Teiler 3, 5 und 15 per Ganzzahldivision die jeweilige Anzahl zulässiger Vielfacher. Für jeden dieser drei Fälle wird die geschlossene Formel \(m\cdot q_m(q_m+1)/2\) ausschließlich mit Ganzzahlarithmetik ausgewertet, also ohne irgendeine Schleife über \(1,2,\dots,N-1\).
Zum Schluss kombiniert die Implementierung die drei Teilsummen als \(S_3+S_5-S_{15}\). Alle drei Versionen prüfen außerdem das bekannte Beispiel \(N=10 \mapsto 23\), und die Standardinstanz von Project Euler verwendet \(N=1000\).
Die Laufzeit beträgt \(O(1)\): Es werden nur konstant viele Ganzzahldivisionen, Multiplikationen, Additionen und eine Subtraktion ausgeführt. Der Speicherbedarf ist ebenfalls \(O(1)\).
Ein naiver Ansatz würde jede Zahl unterhalb von \(N\) einzeln untersuchen und auf Teilbarkeit durch 3 oder 5 testen; das kostet \(O(N)\) Zeit. Die geschlossene Formel beseitigt diese Abhängigkeit von der Größe der Schranke vollständig.
Dışlayıcı üst sınır \(N\) verildiğinde, \(n \lt N\) koşulunu sağlayan ve 3'e ya da 5'e bölünen tüm pozitif tamsayıların toplamı istenir. Tek dikkat edilmesi gereken nokta çakışmadır: hem 3'e hem 5'e bölünen sayılar iki kez değil, bir kez sayılmalıdır.
Uygulamalar bu yüzden \(N\)'nin altındaki her sayıyı tek tek dolaşmaz. Bunun yerine probleme özgü iki yapıyı kullanırlar: sabit bir bölenin katları bir aritmetik dizi oluşturur ve 3 ile 5'in ortak katları tam olarak 15'in katlarıdır.
Her pozitif bölen \(m\) için
$$A_m(N)=\{x\in\mathbb{N}: x \lt N,\; m \mid x\}$$
tanımını yapalım. O zaman aranan toplam
$$\sum_{x \in A_3(N)\cup A_5(N)} x$$
olur.
Temel kümeler \(A_3(N)\) ve \(A_5(N)\)'tir. Bu iki kümenin kesişimi nettir: bir sayı her ikisinde de yer alıyorsa \(\operatorname{lcm}(3,5)=15\)'e bölünüyordur. Dolayısıyla
$$A_3(N)\cap A_5(N)=A_{15}(N).$$
Bütün çözüm bu değişmez yapı üzerine kuruludur. Sonuçta toplamamız gereken şey, 3'ün katları, 5'in katları ve 15'teki örtüşmenin doğru biçimde birleştirilmesidir.
Sabit bir \(m\) böleni alalım. \(N\)'den küçük uygun katlar
$$m,\,2m,\,3m,\,\dots,\,q_m m$$
şeklindedir; burada
$$q_m=\left\lfloor \frac{N-1}{m}\right\rfloor.$$
Burada \(N-1\) kullanılmasının nedeni üst sınırın sıkı olmasıdır. Eşdeğer olarak \(q_m\),
$$q_m m \lt N \le (q_m+1)m$$
koşulunu sağlayan tek tamsayıdır. Bu nedenle uygulamalar her adayı denetlemek yerine yalnızca \(q_m\) sayısını hesaplar.
\(q_m\) bilindiğinde ilgili toplam
$$S_m(N)=\sum_{x\in A_m(N)} x = m(1+2+\cdots+q_m)$$
olur. Üçgensel sayı özdeşliği
$$1+2+\cdots+q_m=\frac{q_m(q_m+1)}{2}$$
kullanılırsa
$$S_m(N)=m\cdot \frac{q_m(q_m+1)}{2}$$
elde edilir. Bu problemde korunacak bir özyineleme yoktur; aritmetik dizi doğrudan sabit zamanda hesaplanan bir kapalı forma çöker.
\(S_3(N)\) ile \(S_5(N)\) toplandığında, 15'in her katı iki kez sayılır. Dahil etme-hariç tutma tam olarak bu fazlalığı siler:
$$\sum_{x \in A_3(N)\cup A_5(N)} x = S_3(N)+S_5(N)-S_{15}(N).$$
Kapalı biçimler yerine konursa
$$\boxed{\sum_{x \in A_3(N)\cup A_5(N)} x= 3\cdot\frac{q_3(q_3+1)}{2} +5\cdot\frac{q_5(q_5+1)}{2} -15\cdot\frac{q_{15}(q_{15}+1)}{2}},$$
burada
$$q_3=\left\lfloor\frac{N-1}{3}\right\rfloor,\qquad q_5=\left\lfloor\frac{N-1}{5}\right\rfloor,\qquad q_{15}=\left\lfloor\frac{N-1}{15}\right\rfloor.$$
İlgili sayılar \(3,5,6,9,10,12,15\) olup doğrudan toplam 60 verir. Formül aynı sonuca tek tek listelemeden ulaşır:
$$q_3=\left\lfloor\frac{15}{3}\right\rfloor=5,\qquad S_3=3\cdot\frac{5\cdot6}{2}=45,$$
$$q_5=\left\lfloor\frac{15}{5}\right\rfloor=3,\qquad S_5=5\cdot\frac{3\cdot4}{2}=30,$$
$$q_{15}=\left\lfloor\frac{15}{15}\right\rfloor=1,\qquad S_{15}=15\cdot\frac{1\cdot2}{2}=15.$$
Dolayısıyla
$$45+30-15=60.$$
\(S_{15}\)'in çıkarılması, 15 değerinin çift sayılmasını engelleyen adımdır.
C++, Python ve Java uygulamaları aynı matematiksel akışı izler. Önce \(N-1\) ifadesi kurulmadan önce \(N=0\) durumu ayrı ele alınır; böylece üst sınırın altında hiç pozitif sayı bulunmayan özel durum güvenli biçimde yönetilir.
Ardından 3, 5 ve 15 için uygun kat sayıları tamsayı bölmesiyle hesaplanır. Her üç bölen için de \(m\cdot q_m(q_m+1)/2\) kapalı formu yalnızca tamsayı aritmetiğiyle değerlendirilir; yani \(1,2,\dots,N-1\) üzerinde hiçbir döngü kurulmaz.
Son aşamada üç kısmi toplam \(S_3+S_5-S_{15}\) biçiminde birleştirilir. Üç uygulama da ayrıca bilinen kontrol örneğini \(N=10 \mapsto 23\) doğrular ve standart Project Euler örneği \(N=1000\) için hesap yapar.
Çalışma süresi \(O(1)\)'dir: sabit sayıda tamsayı bölme, çarpma, toplama ve bir çıkarma yapılır. Bellek kullanımı da \(O(1)\)'dir.
Naif yaklaşım \(N\)'nin altındaki her sayıyı tek tek inceleyip 3 veya 5'e bölünüp bölünmediğini test eder; bu da \(O(N)\) zaman gerektirir. Kapalı form bu bağımlılığı tamamen ortadan kaldırır.
Dado un límite superior exclusivo \(N\), se pide la suma de todos los enteros positivos \(n \lt N\) tales que \(3 \mid n\) o \(5 \mid n\). El único cuidado real es el solapamiento: los números divisibles por ambos no deben contarse dos veces.
Por eso las implementaciones no recorren todos los enteros por debajo de \(N\). Aprovechan dos estructuras muy concretas del problema: los múltiplos de un divisor fijo forman una progresión aritmética, y los múltiplos comunes de 3 y 5 son exactamente los múltiplos de 15.
Para cada divisor positivo \(m\), definimos
$$A_m(N)=\{x\in\mathbb{N}: x \lt N,\; m \mid x\}.$$
Entonces la suma buscada es
$$\sum_{x \in A_3(N)\cup A_5(N)} x.$$
Los conjuntos centrales son \(A_3(N)\) y \(A_5(N)\). Su intersección se identifica de inmediato: un número pertenece a ambos exactamente cuando es divisible por \(\operatorname{lcm}(3,5)=15\). Por tanto,
$$A_3(N)\cap A_5(N)=A_{15}(N).$$
Ese es el invariante estructural de toda la solución. Al final solo hay que sumar correctamente tres familias muy ordenadas: múltiplos de 3, múltiplos de 5 y el solapamiento en 15.
Fijemos un divisor \(m\). Los múltiplos válidos por debajo de \(N\) son
$$m,\,2m,\,3m,\,\dots,\,q_m m,$$
donde
$$q_m=\left\lfloor \frac{N-1}{m}\right\rfloor.$$
La aparición de \(N-1\) es esencial porque la desigualdad es estricta. De forma equivalente, \(q_m\) es el único entero tal que
$$q_m m \lt N \le (q_m+1)m.$$
Así, la implementación no necesita probar uno por uno los candidatos; basta con conocer el conteo \(q_m\).
Una vez conocido \(q_m\), la suma asociada es
$$S_m(N)=\sum_{x\in A_m(N)} x = m(1+2+\cdots+q_m).$$
Usando la identidad triangular
$$1+2+\cdots+q_m=\frac{q_m(q_m+1)}{2},$$
obtenemos
$$S_m(N)=m\cdot \frac{q_m(q_m+1)}{2}.$$
En este problema no aparece ninguna recurrencia ni un estado dinámico complicado. Toda la progresión se colapsa directamente a una expresión de tiempo constante.
Si sumamos \(S_3(N)\) y \(S_5(N)\), cada múltiplo de 15 entra dos veces. El principio de inclusión-exclusión elimina exactamente esa copia extra:
$$\sum_{x \in A_3(N)\cup A_5(N)} x = S_3(N)+S_5(N)-S_{15}(N).$$
Al sustituir las fórmulas cerradas resulta
$$\boxed{\sum_{x \in A_3(N)\cup A_5(N)} x= 3\cdot\frac{q_3(q_3+1)}{2} +5\cdot\frac{q_5(q_5+1)}{2} -15\cdot\frac{q_{15}(q_{15}+1)}{2}},$$
con
$$q_3=\left\lfloor\frac{N-1}{3}\right\rfloor,\qquad q_5=\left\lfloor\frac{N-1}{5}\right\rfloor,\qquad q_{15}=\left\lfloor\frac{N-1}{15}\right\rfloor.$$
Los números relevantes son \(3,5,6,9,10,12,15\), y su suma directa es 60. La fórmula llega al mismo resultado sin enumerarlos uno por uno:
$$q_3=\left\lfloor\frac{15}{3}\right\rfloor=5,\qquad S_3=3\cdot\frac{5\cdot6}{2}=45,$$
$$q_5=\left\lfloor\frac{15}{5}\right\rfloor=3,\qquad S_5=5\cdot\frac{3\cdot4}{2}=30,$$
$$q_{15}=\left\lfloor\frac{15}{15}\right\rfloor=1,\qquad S_{15}=15\cdot\frac{1\cdot2}{2}=15.$$
Por lo tanto,
$$45+30-15=60.$$
La resta de \(S_{15}\) es exactamente lo que evita contar dos veces al 15.
Las implementaciones en C++, Python y Java siguen la misma secuencia matemática. Primero tratan el caso degenerado \(N=0\) antes de formar la expresión \(N-1\); así, el conteo sigue bien definido incluso cuando no hay enteros positivos por debajo del límite.
Después calculan, mediante división entera, cuántos múltiplos válidos hay para 3, 5 y 15. Para cada uno de esos tres divisores evalúan la fórmula cerrada \(m\cdot q_m(q_m+1)/2\) usando solo aritmética entera, de modo que no existe ningún recorrido sobre \(1,2,\dots,N-1\).
Por último, la implementación combina las tres contribuciones como \(S_3+S_5-S_{15}\). Las tres versiones también verifican el punto de control conocido \(N=10 \mapsto 23\), y la instancia estándar de Project Euler usa \(N=1000\).
El tiempo de ejecución es \(O(1)\): solo se realizan un número fijo de divisiones enteras, multiplicaciones, sumas y una resta. El uso de memoria también es \(O(1)\).
Un método ingenuo examinaría todos los enteros menores que \(N\) y comprobaría si son divisibles por 3 o por 5, lo cual cuesta \(O(N)\) tiempo. La fórmula cerrada elimina por completo esa dependencia del tamaño del límite.
给定一个严格上界 \(N\)，要求所有满足 \(n \lt N\) 且能被 3 或 5 整除的正整数之和。真正需要小心的地方只有一个：同时被 3 和 5 整除的数不能重复计数。
因此，代码并不会把 \(N\) 以下的每个整数都检查一遍。它利用了这道题特有的两个数学对象：固定除数的倍数天然构成等差数列，而 3 与 5 的公共倍数恰好就是 15 的倍数。
对每个正整数 \(m\)，定义
$$A_m(N)=\{x\in\mathbb{N}: x \lt N,\; m \mid x\}.$$
那么目标就是
$$\sum_{x \in A_3(N)\cup A_5(N)} x.$$
本题真正需要处理的集合只有 \(A_3(N)\) 与 \(A_5(N)\)。它们的交集并不复杂：一个数同时落在这两个集合中，当且仅当它能被 \(\operatorname{lcm}(3,5)=15\) 整除。因此
$$A_3(N)\cap A_5(N)=A_{15}(N).$$
这就是整道题最重要的结构性不变量。最后需要组合的，其实只有三类有序对象：3 的倍数、5 的倍数，以及作为重叠部分的 15 的倍数。
固定一个除数 \(m\)。所有严格小于 \(N\) 的有效倍数写成
$$m,\,2m,\,3m,\,\dots,\,q_m m,$$
其中
$$q_m=\left\lfloor \frac{N-1}{m}\right\rfloor.$$
这里使用 \(N-1\) 不是形式上的技巧，而是由严格不等式 \(x \lt N\) 决定的。等价地说，\(q_m\) 是满足
$$q_m m \lt N \le (q_m+1)m$$
的唯一整数。也就是说，实现根本不必逐个测试候选值，只要先算出这个计数 \(q_m\) 即可。
知道 \(q_m\) 以后，对应的部分和就是
$$S_m(N)=\sum_{x\in A_m(N)} x = m(1+2+\cdots+q_m).$$
再利用三角数恒等式
$$1+2+\cdots+q_m=\frac{q_m(q_m+1)}{2},$$
立刻得到
$$S_m(N)=m\cdot \frac{q_m(q_m+1)}{2}.$$
对这道题来说，并不存在需要维护的递推关系，也不需要动态规划。问题的本质就是把三个等差数列的和直接折叠成常数时间公式。
如果直接把 \(S_3(N)\) 与 \(S_5(N)\) 相加，那么每个 15 的倍数都会被算两次。容斥原理恰好删去这多出来的一次：
$$\sum_{x \in A_3(N)\cup A_5(N)} x = S_3(N)+S_5(N)-S_{15}(N).$$
把闭式全部代入以后，可得
$$\boxed{\sum_{x \in A_3(N)\cup A_5(N)} x= 3\cdot\frac{q_3(q_3+1)}{2} +5\cdot\frac{q_5(q_5+1)}{2} -15\cdot\frac{q_{15}(q_{15}+1)}{2}},$$
其中
$$q_3=\left\lfloor\frac{N-1}{3}\right\rfloor,\qquad q_5=\left\lfloor\frac{N-1}{5}\right\rfloor,\qquad q_{15}=\left\lfloor\frac{N-1}{15}\right\rfloor.$$
此时相关整数是 \(3,5,6,9,10,12,15\)，直接求和得到 60。闭式公式无需逐项枚举，也能得出完全相同的结果：
$$q_3=\left\lfloor\frac{15}{3}\right\rfloor=5,\qquad S_3=3\cdot\frac{5\cdot6}{2}=45,$$
$$q_5=\left\lfloor\frac{15}{5}\right\rfloor=3,\qquad S_5=5\cdot\frac{3\cdot4}{2}=30,$$
$$q_{15}=\left\lfloor\frac{15}{15}\right\rfloor=1,\qquad S_{15}=15\cdot\frac{1\cdot2}{2}=15.$$
所以
$$45+30-15=60.$$
减去 \(S_{15}\) 的意义非常具体：它正是把数字 15 的那一次重复计数消掉。
C++、Python 和 Java 三个实现遵循完全相同的数学流程。第一步是在构造 \(N-1\) 之前先处理 \(N=0\) 这个退化情形，这样即使上界以下没有任何正整数，后续计数仍然是定义良好的。
接着，它们用整数除法分别求出 3、5、15 这三个除数对应的有效倍数个数。然后对每个除数都直接代入闭式 \(m\cdot q_m(q_m+1)/2\)，整个计算过程只使用整数运算，不会遍历 \(1,2,\dots,N-1\) 这一长段区间。
最后一步是按 \(S_3+S_5-S_{15}\) 组合三部分结果。三个实现都验证了标准检查点 \(N=10 \mapsto 23\)，而标准 Project Euler 实例使用的是 \(N=1000\)。
时间复杂度是 \(O(1)\)：算法只做固定次数的整数除法、乘法、加法和一次减法。空间复杂度同样是 \(O(1)\)。
朴素方法需要检查所有小于 \(N\) 的整数，看它们是否能被 3 或 5 整除，因此时间复杂度为 \(O(N)\)。闭式公式把这种对输入规模的线性依赖彻底消除了。
Для строгой верхней границы \(N\) требуется найти сумму всех положительных целых \(n \lt N\), для которых выполнено \(3 \mid n\) или \(5 \mid n\). Единственный тонкий момент связан с пересечением: числа, кратные и 3, и 5, должны учитываться ровно один раз.
Поэтому реализации не перебирают все числа ниже \(N\). Они используют две конкретные структуры этой задачи: кратные фиксированного делителя образуют арифметическую прогрессию, а общие кратные 3 и 5 совпадают с кратными 15.
Для каждого положительного делителя \(m\) введем множество
$$A_m(N)=\{x\in\mathbb{N}: x \lt N,\; m \mid x\}.$$
Тогда искомая сумма равна
$$\sum_{x \in A_3(N)\cup A_5(N)} x.$$
Нас интересуют \(A_3(N)\) и \(A_5(N)\). Их пересечение определяется сразу: число лежит в обоих множествах тогда и только тогда, когда делится на \(\operatorname{lcm}(3,5)=15\). Следовательно,
$$A_3(N)\cap A_5(N)=A_{15}(N).$$
Это и есть основная структурная инварианта решения. Вся задача сводится к корректному комбинированию трех упорядоченных сумм: кратных 3, кратных 5 и кратных 15 как области пересечения.
Зафиксируем делитель \(m\). Тогда все допустимые кратные ниже \(N\) имеют вид
$$m,\,2m,\,3m,\,\dots,\,q_m m,$$
где
$$q_m=\left\lfloor \frac{N-1}{m}\right\rfloor.$$
Появление \(N-1\) принципиально, потому что ограничение строгое. Эквивалентно, \(q_m\) является единственным целым, удовлетворяющим
$$q_m m \lt N \le (q_m+1)m.$$
Поэтому реализациям не нужно проверять кандидатов по одному; достаточно вычислить только число допустимых кратных \(q_m\).
Когда \(q_m\) известно, соответствующая сумма равна
$$S_m(N)=\sum_{x\in A_m(N)} x = m(1+2+\cdots+q_m).$$
Используя тождество для треугольных чисел
$$1+2+\cdots+q_m=\frac{q_m(q_m+1)}{2},$$
получаем
$$S_m(N)=m\cdot \frac{q_m(q_m+1)}{2}.$$
Здесь нет ни рекуррентного соотношения, ни сложного состояния. Суть задачи в том, что каждая прогрессия сразу схлопывается в формулу константной стоимости.
Если просто сложить \(S_3(N)\) и \(S_5(N)\), то каждое кратное 15 будет учтено дважды. Принцип включений-исключений убирает ровно этот лишний экземпляр:
$$\sum_{x \in A_3(N)\cup A_5(N)} x = S_3(N)+S_5(N)-S_{15}(N).$$
После подстановки закрытых форм получаем
$$\boxed{\sum_{x \in A_3(N)\cup A_5(N)} x= 3\cdot\frac{q_3(q_3+1)}{2} +5\cdot\frac{q_5(q_5+1)}{2} -15\cdot\frac{q_{15}(q_{15}+1)}{2}},$$
где
$$q_3=\left\lfloor\frac{N-1}{3}\right\rfloor,\qquad q_5=\left\lfloor\frac{N-1}{5}\right\rfloor,\qquad q_{15}=\left\lfloor\frac{N-1}{15}\right\rfloor.$$
Подходящие числа: \(3,5,6,9,10,12,15\). Их прямая сумма равна 60. Формула дает тот же результат без пошагового перечисления:
$$q_3=\left\lfloor\frac{15}{3}\right\rfloor=5,\qquad S_3=3\cdot\frac{5\cdot6}{2}=45,$$
$$q_5=\left\lfloor\frac{15}{5}\right\rfloor=3,\qquad S_5=5\cdot\frac{3\cdot4}{2}=30,$$
$$q_{15}=\left\lfloor\frac{15}{15}\right\rfloor=1,\qquad S_{15}=15\cdot\frac{1\cdot2}{2}=15.$$
Следовательно,
$$45+30-15=60.$$
Вычитание \(S_{15}\) и есть тот шаг, который не позволяет числу 15 войти в ответ два раза.
Реализации на C++, Python и Java проходят одну и ту же математическую цепочку. Сначала они отдельно обрабатывают случай \(N=0\), прежде чем формировать выражение \(N-1\); это гарантирует корректность даже тогда, когда ниже границы нет ни одного положительного числа.
Затем с помощью целочисленного деления вычисляется количество допустимых кратных для 3, 5 и 15. Для каждого из этих трех делителей реализация подставляет значение в формулу \(m\cdot q_m(q_m+1)/2\), так что все вычисление ведется в целых числах и без цикла по \(1,2,\dots,N-1\).
После этого три частичные суммы объединяются как \(S_3+S_5-S_{15}\). Во всех трех версиях также проверяется стандартная контрольная точка \(N=10 \mapsto 23\), а стандартный экземпляр Project Euler соответствует \(N=1000\).
Время работы равно \(O(1)\): выполняется фиксированное число целочисленных делений, умножений, сложений и одно вычитание. Память тоже \(O(1)\).
Наивный метод проверял бы каждое число ниже \(N\) на делимость на 3 или 5, что требует \(O(N)\) времени. Закрытая формула полностью убирает эту линейную зависимость от размера входа.
لدينا حد أعلى حصري \(N\)، والمطلوب هو مجموع جميع الأعداد الصحيحة الموجبة \(n \lt N\) التي تحقق \(3 \mid n\) أو \(5 \mid n\). النقطة الدقيقة الوحيدة هي مسألة التداخل: الأعداد القابلة للقسمة على 3 و5 معًا يجب أن تدخل مرة واحدة فقط.
لهذا السبب لا تقوم التطبيقات بفحص كل عدد أصغر من \(N\) على حدة. بل تعتمد على بنيتين رياضيتين واضحتين في هذه المسألة: مضاعفات قاسم ثابت تشكل متتالية حسابية، والمضاعفات المشتركة للعددين 3 و5 هي بالضبط مضاعفات 15.
لكل قاسم موجب \(m\)، نعرّف
$$A_m(N)=\{x\in\mathbb{N}: x \lt N,\; m \mid x\}.$$
وعندئذ يصبح المطلوب
$$\sum_{x \in A_3(N)\cup A_5(N)} x.$$
المجموعتان الأساسيتان هما \(A_3(N)\) و\(A_5(N)\). أما تقاطعهما فمحدد تمامًا: ينتمي عدد إلى المجموعتين معًا إذا وفقط إذا كان قابلاً للقسمة على \(\operatorname{lcm}(3,5)=15\). لذلك
$$A_3(N)\cap A_5(N)=A_{15}(N).$$
هذه هي البنية الثابتة التي يحملها الحل كله. فالمسألة لا تحتاج إلا إلى تجميع ثلاث مجموعات منظمة: مضاعفات 3، ومضاعفات 5، ومنطقة التداخل عند مضاعفات 15.
لنثبت قاسمًا \(m\). عندئذ تكون المضاعفات المسموح بها الأصغر من \(N\) هي
$$m,\,2m,\,3m,\,\dots,\,q_m m,$$
حيث
$$q_m=\left\lfloor \frac{N-1}{m}\right\rfloor.$$
ظهور \(N-1\) هنا ضروري لأن الحد صارم. وبصورة مكافئة، فإن \(q_m\) هو العدد الصحيح الوحيد الذي يحقق
$$q_m m \lt N \le (q_m+1)m.$$
إذًا لا تحتاج التطبيقات إلى اختبار كل مرشح منفردًا؛ يكفيها حساب عدد المضاعفات الصحيحة \(q_m\).
بعد معرفة \(q_m\)، يصبح المجموع الجزئي المقابل
$$S_m(N)=\sum_{x\in A_m(N)} x = m(1+2+\cdots+q_m).$$
وباستخدام هوية الأعداد المثلثية
$$1+2+\cdots+q_m=\frac{q_m(q_m+1)}{2},$$
نحصل على
$$S_m(N)=m\cdot \frac{q_m(q_m+1)}{2}.$$
في هذه المسألة لا توجد علاقة عودية يجب تتبعها، ولا حالة ديناميكية معقدة. الفكرة كلها أن متتالية المضاعفات تنضغط مباشرة إلى تعبير ذي كلفة ثابتة.
إذا جمعنا \(S_3(N)\) و\(S_5(N)\) مباشرة، فإن كل مضاعف لـ 15 سيُحسب مرتين. مبدأ الشمول والاستبعاد يزيل هذه النسخة الزائدة بالضبط:
$$\sum_{x \in A_3(N)\cup A_5(N)} x = S_3(N)+S_5(N)-S_{15}(N).$$
وبتعويض الصيغ المغلقة نحصل على
$$\boxed{\sum_{x \in A_3(N)\cup A_5(N)} x= 3\cdot\frac{q_3(q_3+1)}{2} +5\cdot\frac{q_5(q_5+1)}{2} -15\cdot\frac{q_{15}(q_{15}+1)}{2}},$$
حيث
$$q_3=\left\lfloor\frac{N-1}{3}\right\rfloor,\qquad q_5=\left\lfloor\frac{N-1}{5}\right\rfloor,\qquad q_{15}=\left\lfloor\frac{N-1}{15}\right\rfloor.$$
الأعداد المعنية هي \(3,5,6,9,10,12,15\)، ومجموعها المباشر يساوي 60. الصيغة المغلقة تصل إلى النتيجة نفسها من دون تعداد خطي:
$$q_3=\left\lfloor\frac{15}{3}\right\rfloor=5,\qquad S_3=3\cdot\frac{5\cdot6}{2}=45,$$
$$q_5=\left\lfloor\frac{15}{5}\right\rfloor=3,\qquad S_5=5\cdot\frac{3\cdot4}{2}=30,$$
$$q_{15}=\left\lfloor\frac{15}{15}\right\rfloor=1,\qquad S_{15}=15\cdot\frac{1\cdot2}{2}=15.$$
وعليه
$$45+30-15=60.$$
طرح \(S_{15}\) هو بالضبط الخطوة التي تمنع احتساب العدد 15 مرتين.
تتبع تطبيقات C++ وPython وJava السلسلة الرياضية نفسها. أولًا تُعالِج الحالة الحدية \(N=0\) قبل تكوين التعبير \(N-1\)، حتى يبقى العد معرفًا بصورة سليمة عندما لا توجد أعداد موجبة أصغر من الحد.
بعد ذلك تُحسب أعداد المضاعفات الصحيحة للقواسم 3 و5 و15 باستخدام القسمة الصحيحة. ثم تُطبّق الصيغة المغلقة \(m\cdot q_m(q_m+1)/2\) على كل قاسم من هذه القواسم الثلاثة، ولذلك يتم الحساب كله بأعداد صحيحة ومن دون أي حلقة تمر على \(1,2,\dots,N-1\).
وفي النهاية تُجمع النتائج الثلاث على الصورة \(S_3+S_5-S_{15}\). كما تتحقق الإصدارات الثلاثة من نقطة الفحص المعروفة \(N=10 \mapsto 23\)، بينما تستعمل المسألة القياسية في Project Euler القيمة \(N=1000\).
زمن التنفيذ هو \(O(1)\): عدد ثابت من عمليات القسمة الصحيحة والضرب والجمع وعملية طرح واحدة. واستهلاك الذاكرة أيضًا \(O(1)\).
أما الطريقة الساذجة فستفحص كل عدد أصغر من \(N\) لتقرر هل يقبل القسمة على 3 أو 5، وهذا يتطلب \(O(N)\) زمنًا. الصيغة المغلقة تزيل هذا الاعتماد الخطي على حجم الحد الأعلى.