For a fixed length \(n\), call the interval \([a,a+n-1]\) divisible if its \(n\) terms can be reordered so that the \(k\)-th chosen term is divisible by \(k\) for every \(1\le k\le n\). Problem 896 asks for the \(36\)th starting value \(a\) when \(n=36\).
Equivalently, we need distinct offsets \(o_1,\dots,o_n\in\{0,\dots,n-1\}\) such that
$$a+o_d \equiv 0 \pmod d \qquad (1\le d\le n).$$
The implementations avoid scanning intervals one by one. Instead they turn each interval into a bipartite matching problem and exploit the fact that the whole condition is periodic modulo \(\operatorname{lcm}(1,2,\dots,n)\).
The key observation is that the problem depends only on which divisibility residues appear inside one block of length \(n\). Once that is rewritten as a matching problem, periodicity and prime-power decomposition reduce the search to a manageable finite computation.
For a start value \(a\), define a bipartite graph with left side \(D=\{1,2,\dots,n\}\) and right side \(O=\{0,1,\dots,n-1\}\). Connect divisor \(d\) to offset \(o\) when
$$a+o \equiv 0 \pmod d.$$
A perfect matching in this graph chooses a distinct interval position for every divisor \(d\). Therefore \([a,a+n-1]\) is divisible if and only if this graph has a perfect matching. Hall's marriage theorem is the mathematical existence criterion, and the implementations test it algorithmically with augmenting paths.
For each fixed \(d\), the edge relation only depends on \(a \bmod d\). Hence the whole graph depends only on \(a \bmod L\), where
$$L=\operatorname{lcm}(1,2,\dots,n)=\prod_{p\le n} p^{\lfloor \log_p n\rfloor}.$$
So if \(a\) works, then \(a+L\) works as well. Let the valid starts in one period be
$$1\le r_1\lt r_2\lt \dots\lt r_P\le L.$$
Then the full infinite sequence of divisible-range starts is periodic:
$$a_k=\left\lfloor\frac{k-1}{P}\right\rfloor L+r_{1+((k-1)\bmod P)}.$$
Thus the problem reduces to enumerating the valid residues in a single period.
Instead of checking all residues modulo \(L\) at once, the implementations build them incrementally. Write \(L\) as a product of pairwise coprime maximal prime powers
$$L=\prod_{p\le n} q_p,\qquad q_p=p^{\lfloor \log_p n\rfloor}.$$
After some of these factors have been processed, let \(M\) be their product and suppose we only know \(a\equiv c \pmod M\). For a divisor \(d\), the processed part of the divisibility condition is exactly
$$\delta_M(d)=\gcd(M,d).$$
Indeed, \(\delta_M(d)\) keeps precisely the prime-power contributions to \(d\) that are already present in \(M\). So an offset \(o\) is still compatible with residue class \(c \bmod M\) whenever
$$c+o \equiv 0 \pmod{\delta_M(d)}.$$
This gives a relaxed matching problem: it enforces all processed prime-power constraints and ignores the rest until later stages. Every exact solution survives all relaxed stages, and once \(M=L\) the relaxed problem becomes the original one.
Suppose the next prime-power factor is \(q\), so the new modulus is \(Mq\). Because \(\gcd(M,q)=1\), every extension of \(c \pmod M\) to modulo \(Mq\) has the form
$$c+kM \qquad (0\le k\lt q).$$
Each candidate is tested by building the relaxed graph with divisor conditions modulo \(\gcd(Mq,d)\). If that relaxed graph has no perfect matching, the residue class cannot lead to a valid full residue and is discarded immediately.
This branch-and-prune process is far smaller than brute force over all \(L\) residues. By the final stage, the survivors are exactly the valid starts in one period.
Take \(n=4\). Then \(L=\operatorname{lcm}(1,2,3,4)=12\). Consider the interval starting at \(a=6\), namely \(\{6,7,8,9\}\). The allowed offsets are
$$\begin{aligned} d=1&:& \{0,1,2,3\},\\ d=2&:& \{0,2\},\\ d=3&:& \{0,3\},\\ d=4&:& \{2\}. \end{aligned}$$
A perfect matching exists: divisor \(4\) must use offset \(2\) (the number \(8\)), divisor \(3\) can use offset \(3\) (the number \(9\)), divisor \(2\) then uses offset \(0\) (the number \(6\)), and divisor \(1\) takes the remaining offset \(1\) (the number \(7\)). So \(a=6\) is a valid start.
By contrast, for \(a=5\) the interval is \(\{5,6,7,8\}\) and the critical offsets are
$$d=2:\{1,3\},\qquad d=3:\{1\},\qquad d=4:\{3\}.$$
The divisors \(2,3,4\) together can only use the two offsets \(\{1,3\}\), so Hall's condition fails. This shows exactly why some residues survive the periodic search and others are pruned away.
The C++, Python, and Java implementations all follow the same pipeline. First they compute \(L\) indirectly as the product of the maximal prime powers up to \(n\). Those same prime powers define the staged moduli used during residue construction.
Next they precompute, for every divisor target \(d\), every divisor \(m\mid d\), and every residue \(r\bmod m\), the bitmask of offsets \(o\in\{0,\dots,n-1\}\) satisfying
$$o+r \equiv 0 \pmod m.$$
This cache means that when a residue class \(c \pmod M\) is tested, the implementation can assemble all allowed offset masks immediately from \(\gcd(M,d)\) and \(c \bmod \gcd(M,d)\).
For each staged modulus, the implementation extends every surviving residue \(c\) to all \(c+kM\) under the next prime-power factor. Each extension yields one bipartite graph on divisors versus offsets. The graph is represented as bit masks, the divisor side is processed from the most constrained masks to the least constrained ones, and a standard augmenting-path matcher checks whether a perfect matching exists.
After the final modulus reaches \(L\), the surviving residues are the exact valid starts within one period. Sorting them gives \(r_1,\dots,r_P\), and the periodic formula above returns the required \(k\)-th start. For Problem 896 the implementations evaluate this with \(n=36\) and \(k=36\).
Let \(n\) be the range length and let \(R\) be the total number of residue classes examined across all stages of the prime-power refinement. Computing the prime list and the maximal prime powers up to \(n\) costs \(O(n\log\log n)\) time and \(O(n)\) memory.
The mask cache requires
$$\sum_{d=1}^{n}\sum_{m\mid d} O(mn)$$
time to build, because for each pair \((d,m)\) every residue class modulo \(m\) is expanded across all \(n\) offsets. This is \(O(n^3)\) in the worst case for generic \(n\), but here \(n=36\) is small and fixed. Its storage is
$$\sum_{d=1}^{n}\sum_{m\mid d} O(m),$$
which is quadratic-scale in practice.
Each residue test builds \(n\) masks and runs a DFS-based bipartite matching on an \(n\times n\) graph, giving \(O(n^3)\) worst-case time per candidate residue. The total search is therefore \(O(Rn^3)\), with \(R\) kept manageable by strong pruning at early modular stages. That is why the approach is practical even though a naive scan over all intervals would be hopeless.
Für eine feste Länge \(n\) heißt das Intervall \([a,a+n-1]\) teilbar, wenn sich seine \(n\) Zahlen so umordnen lassen, dass die \(k\)-te gewählte Zahl für jedes \(1\le k\le n\) durch \(k\) teilbar ist. In Problem 896 wird der \(36\). Startwert \(a\) für den Fall \(n=36\) gesucht.
Äquivalent dazu brauchen wir paarweise verschiedene Offsets \(o_1,\dots,o_n\in\{0,\dots,n-1\}\) mit
$$a+o_d \equiv 0 \pmod d \qquad (1\le d\le n).$$
Die Implementierungen vermeiden es, Intervalle einzeln zu testen. Stattdessen übersetzen sie jedes Intervall in ein bipartites Matching-Problem und nutzen aus, dass die gesamte Bedingung modulo \(\operatorname{lcm}(1,2,\dots,n)\) periodisch ist.
Der entscheidende Punkt ist, dass das Problem nicht von den absoluten Größen der Zahlen abhängt, sondern nur davon, welche Teilbarkeitsreste in einem Block der Länge \(n\) auftreten. Sobald das als Matching formuliert ist, reduzieren Periodizität und Primzahlpotenz-Zerlegung die Suche auf eine endliche und gut beherrschbare Rechnung.
Zu einem Startwert \(a\) definieren wir einen bipartiten Graphen mit linker Seite \(D=\{1,2,\dots,n\}\) und rechter Seite \(O=\{0,1,\dots,n-1\}\). Ein Teiler \(d\) ist mit einem Offset \(o\) verbunden, genau dann wenn
$$a+o \equiv 0 \pmod d.$$
Ein perfektes Matching in diesem Graphen wählt für jeden Teiler \(d\) eine eigene Position im Intervall. Daher ist \([a,a+n-1]\) genau dann teilbar, wenn dieser Graph ein perfektes Matching besitzt. Der theoretische Existenzsatz ist der Heiratssatz von Hall; die Implementierungen prüfen die Bedingung algorithmisch mit augmentierenden Pfaden.
Für festes \(d\) hängt die Kantenrelation nur von \(a \bmod d\) ab. Also hängt der gesamte Graph nur von \(a \bmod L\) ab, wobei
$$L=\operatorname{lcm}(1,2,\dots,n)=\prod_{p\le n} p^{\lfloor \log_p n\rfloor}.$$
Wenn also \(a\) funktioniert, dann funktioniert auch \(a+L\). Bezeichnen wir die gültigen Startwerte innerhalb einer Periode mit
$$1\le r_1\lt r_2\lt \dots\lt r_P\le L,$$
dann ist die unendliche Folge aller Startwerte periodisch:
$$a_k=\left\lfloor\frac{k-1}{P}\right\rfloor L+r_{1+((k-1)\bmod P)}.$$
Damit reduziert sich das Problem auf die Bestimmung der gültigen Restklassen in genau einer Periode.
Statt alle Restklassen modulo \(L\) auf einmal zu prüfen, bauen die Implementierungen sie schrittweise auf. Schreibe \(L\) als Produkt paarweise teilerfremder maximaler Primzahlpotenzen
$$L=\prod_{p\le n} q_p,\qquad q_p=p^{\lfloor \log_p n\rfloor}.$$
Nachdem einige dieser Faktoren verarbeitet sind, sei \(M\) ihr Produkt und wir kennen nur \(a\equiv c \pmod M\). Für einen Teiler \(d\) ist der bereits festgelegte Teil der Teilbarkeitsbedingung genau
$$\delta_M(d)=\gcd(M,d).$$
Denn \(\delta_M(d)\) enthält genau die Primzahlpotenz-Anteile von \(d\), die schon in \(M\) stecken. Ein Offset \(o\) bleibt also mit der Restklasse \(c \bmod M\) verträglich, wenn
$$c+o \equiv 0 \pmod{\delta_M(d)}.$$
So entsteht ein relaxiertes Matching-Problem: Alle bereits verarbeiteten Primzahlpotenzen werden erzwungen, die übrigen erst in späteren Stufen. Jede exakte Lösung überlebt jede relaxierte Stufe, und bei \(M=L\) fällt das relaxierte Problem mit dem ursprünglichen zusammen.
Sei \(q\) die nächste Primzahlpotenz, also ist der neue Modul \(Mq\). Wegen \(\gcd(M,q)=1\) hat jede Erweiterung von \(c \pmod M\) zu modulo \(Mq\) die Form
$$c+kM \qquad (0\le k\lt q).$$
Jeder Kandidat wird getestet, indem der relaxierte Graph mit Teilbarkeitsbedingungen modulo \(\gcd(Mq,d)\) aufgebaut wird. Hat dieser Graph kein perfektes Matching, dann kann die Restklasse niemals zu einer gültigen vollständigen Restklasse führen und wird sofort verworfen.
Dieses Branch-and-Prune-Verfahren ist viel kleiner als rohe Gewalt über alle \(L\) Restklassen. In der letzten Stufe sind die Überlebenden genau die gültigen Startwerte innerhalb einer Periode.
Nehmen wir \(n=4\). Dann ist \(L=\operatorname{lcm}(1,2,3,4)=12\). Betrachte das Intervall mit Start \(a=6\), also \(\{6,7,8,9\}\). Die erlaubten Offsets sind
$$\begin{aligned} d=1&:& \{0,1,2,3\},\\ d=2&:& \{0,2\},\\ d=3&:& \{0,3\},\\ d=4&:& \{2\}. \end{aligned}$$
Ein perfektes Matching existiert: Der Teiler \(4\) muss Offset \(2\) verwenden (die Zahl \(8\)), der Teiler \(3\) kann Offset \(3\) verwenden (die Zahl \(9\)), der Teiler \(2\) nimmt dann Offset \(0\) (die Zahl \(6\)), und der Teiler \(1\) erhält den verbleibenden Offset \(1\) (die Zahl \(7\)). Also ist \(a=6\) ein gültiger Startwert.
Für \(a=5\) ist das Intervall dagegen \(\{5,6,7,8\}\), und die kritischen Offsets sind
$$d=2:\{1,3\},\qquad d=3:\{1\},\qquad d=4:\{3\}.$$
Die Teiler \(2,3,4\) zusammen können also nur die zwei Offsets \(\{1,3\}\) benutzen, daher scheitert die Hall-Bedingung. Genau daran sieht man, warum einige Restklassen die periodische Suche überleben und andere früh ausscheiden.
Die Implementierungen in C++, Python und Java folgen derselben Pipeline. Zuerst berechnen sie \(L\) indirekt als Produkt der maximalen Primzahlpotenzen bis \(n\). Dieselben Primzahlpotenzen definieren auch die Stufenmoduli während der Konstruktion der Restklassen.
Anschließend wird für jedes Teilerziel \(d\), jeden Teiler \(m\mid d\) und jeden Rest \(r\bmod m\) die Bitmaske der Offsets \(o\in\{0,\dots,n-1\}\) vorab berechnet, die
$$o+r \equiv 0 \pmod m$$
erfüllen. Dadurch kann die Implementierung beim Testen einer Restklasse \(c \pmod M\) alle erlaubten Offset-Masken sofort aus \(\gcd(M,d)\) und \(c \bmod \gcd(M,d)\) zusammensetzen.
Für jeden Stufenmodul erweitert die Implementierung jede überlebende Restklasse \(c\) zu allen \(c+kM\) unter dem nächsten Primzahlpotenzfaktor. Jede Erweiterung erzeugt genau einen bipartiten Graphen zwischen Teilern und Offsets. Der Graph wird als Bitmasken gespeichert, die Teilerseite wird von den engsten Masken zu den lockersten abgearbeitet, und ein Standard-Matcher mit augmentierenden Pfaden prüft, ob ein perfektes Matching existiert.
Sobald der letzte Modul \(L\) erreicht ist, sind die überlebenden Restklassen exakt die gültigen Startwerte innerhalb einer Periode. Nach dem Sortieren erhält man \(r_1,\dots,r_P\), und die periodische Formel oben liefert den gesuchten \(k\)-ten Startwert. Für Problem 896 setzen die Implementierungen dabei \(n=36\) und \(k=36\).
Sei \(n\) die Intervalllänge und \(R\) die Gesamtzahl der Restklassen, die über alle Stufen der Primzahlpotenz-Verfeinerung hinweg geprüft werden. Das Berechnen der Primzahlen und maximalen Primzahlpotenzen bis \(n\) kostet \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher.
Der Aufbau des Masken-Caches benötigt
$$\sum_{d=1}^{n}\sum_{m\mid d} O(mn)$$
Zeit, denn für jedes Paar \((d,m)\) wird jede Restklasse modulo \(m\) über alle \(n\) Offsets ausgewertet. Für generisches \(n\) ist das im schlechtesten Fall \(O(n^3)\), hier aber mit \(n=36\) klein und fest. Der Speicherbedarf beträgt
$$\sum_{d=1}^{n}\sum_{m\mid d} O(m),$$
also praktisch Größenordnung quadratisch.
Jeder Restklassentest baut \(n\) Masken und führt ein bipartites Matching per Tiefensuche auf einem \(n\times n\)-Graphen aus. Das ergibt im schlechtesten Fall \(O(n^3)\) Zeit pro Kandidat. Insgesamt kostet die Suche also \(O(Rn^3)\), wobei \(R\) durch starkes frühes Pruning klein gehalten wird. Genau deshalb ist der Ansatz praktikabel, obwohl eine naive Durchmusterung aller Intervalle aussichtslos wäre.
Sabit bir \(n\) uzunluğu için \([a,a+n-1]\) aralığına, içindeki \(n\) sayı yeniden sıralanabildiğinde ve seçilen \(k\). sayı her \(1\le k\le n\) için \(k\) ile bölünebildiğinde bölünebilir aralık diyelim. Problem 896, \(n=36\) iken bu özelliği sağlayan \(36\). başlangıç değeri \(a\)'yı sorar.
Buna eşdeğer olarak, \(\{0,\dots,n-1\}\) içinden birbirinden farklı ofsetler \(o_1,\dots,o_n\) bulmamız gerekir ve
$$a+o_d \equiv 0 \pmod d \qquad (1\le d\le n)$$
olmalıdır. Uygulamalar aralıkları tek tek taramaz. Bunun yerine her aralığı iki parçalı bir eşleme problemine dönüştürür ve tüm koşulun \(\operatorname{lcm}(1,2,\dots,n)\) modunda periyodik olmasından yararlanır.
Temel gözlem şudur: problem sayılarının mutlak büyüklüklerinden değil, uzunluğu \(n\) olan bir blok içinde hangi bölünebilirlik kalıntılarının göründüğünden etkilenir. Bu durum eşleme problemine çevrilince, periyodiklik ve asal kuvvet ayrışımı aramayı sonlu ve yönetilebilir bir hesaba indirir.
Bir başlangıç değeri \(a\) için sol tarafta \(D=\{1,2,\dots,n\}\), sağ tarafta \(O=\{0,1,\dots,n-1\}\) olan iki parçalı bir grafik tanımlayalım. Bölen \(d\) ile ofset \(o\) arasında, ancak ve ancak
$$a+o \equiv 0 \pmod d$$
ise kenar olsun. Bu grafikteki tam eşleme, her bölen \(d\) için aralıkta farklı bir konum seçer. Dolayısıyla \([a,a+n-1]\) aralığı ancak ve ancak grafik tam eşleme içeriyorsa bölünebilirdir. Kuramsal varlık ölçütü Hall evlilik teoremidir; uygulamalar bunu artırıcı yollarla algoritmik olarak test eder.
Sabit bir \(d\) için kenar koşulu yalnızca \(a \bmod d\)'ye bağlıdır. Bu yüzden tüm grafik yalnızca \(a \bmod L\)'ye bağlıdır; burada
$$L=\operatorname{lcm}(1,2,\dots,n)=\prod_{p\le n} p^{\lfloor \log_p n\rfloor}.$$
Demek ki \(a\) çalışıyorsa \(a+L\) de çalışır. Bir periyot içindeki geçerli başlangıçlar
$$1\le r_1\lt r_2\lt \dots\lt r_P\le L$$
olsun. O zaman tüm sonsuz başlangıç dizisi periyodiktir:
$$a_k=\left\lfloor\frac{k-1}{P}\right\rfloor L+r_{1+((k-1)\bmod P)}.$$
Böylece problem, tek bir periyot içindeki geçerli kalıntıları bulmaya indirgenir.
Uygulamalar \(L\) modundaki tüm kalıntıları tek seferde denemez. Bunun yerine \(L\)'yi aralarında aralarında asal olan en büyük asal kuvvetlerin çarpımı olarak yazar:
$$L=\prod_{p\le n} q_p,\qquad q_p=p^{\lfloor \log_p n\rfloor}.$$
Bu çarpanların bir kısmı işlendiğinde modül \(M\) olsun ve yalnızca \(a\equiv c \pmod M\) bilgisini biliyor olalım. Bir bölen \(d\) için bölünebilirlik koşulunun işlenmiş kısmı tam olarak
$$\delta_M(d)=\gcd(M,d)$$
değeridir. Çünkü \(\delta_M(d)\), \(d\) içindeki ve halihazırda \(M\)'ye dahil edilmiş asal kuvvetleri tam olarak ayıklar. Bu yüzden bir ofset \(o\),
$$c+o \equiv 0 \pmod{\delta_M(d)}$$
olduğu sürece \(c \bmod M\) kalıntı sınıfıyla uyumludur. Böylece gevşetilmiş bir eşleme problemi elde edilir: işlenmiş asal kuvvetler zorlanır, geri kalanlar sonraki aşamalara bırakılır. Her kesin çözüm tüm gevşetilmiş aşamalardan geçer; \(M=L\) olduğunda gevşetilmiş problem asıl problemle aynı hale gelir.
Sıradaki asal kuvvet \(q\) olsun; yeni modül \(Mq\) olur. \(\gcd(M,q)=1\) olduğundan, \(c \pmod M\) kalıntısının modulo \(Mq\)'daki tüm uzantıları
$$c+kM \qquad (0\le k\lt q)$$
biçimindedir. Her aday için, bölen koşulları \(\gcd(Mq,d)\) modunda kurulan gevşetilmiş grafik test edilir. Bu grafik tam eşleme içermiyorsa, ilgili kalıntı sınıfı hiçbir zaman tam bir geçerli kalıntıya dönüşemez ve anında elenir.
Bu dallanma ve budama süreci, tüm \(L\) kalıntılarını kaba kuvvetle taramaktan çok daha küçüktür. Son aşamada elde kalanlar, tek periyottaki gerçek başlangıçlardır.
\(n=4\) alalım. Bu durumda \(L=\operatorname{lcm}(1,2,3,4)=12\). \(a=6\) ile başlayan aralığı, yani \(\{6,7,8,9\}\) kümesini ele alalım. Uygun ofsetler şunlardır:
$$\begin{aligned} d=1&:& \{0,1,2,3\},\\ d=2&:& \{0,2\},\\ d=3&:& \{0,3\},\\ d=4&:& \{2\}. \end{aligned}$$
Burada tam eşleme vardır: \(4\) böleni mecburen ofset \(2\)'yi kullanır (sayı \(8\)), \(3\) böleni ofset \(3\)'ü kullanabilir (sayı \(9\)), \(2\) böleni ofset \(0\)'ı alır (sayı \(6\)), \(1\) böleni de kalan ofset \(1\)'i alır (sayı \(7\)). Bu yüzden \(a=6\) geçerli bir başlangıçtır.
Buna karşılık \(a=5\) için aralık \(\{5,6,7,8\}\) olur ve kritik ofsetler
$$d=2:\{1,3\},\qquad d=3:\{1\},\qquad d=4:\{3\}$$
şeklindedir. Yani \(2,3,4\) bölenleri birlikte yalnızca \(\{1,3\}\) ofsetlerini kullanabilir; Hall koşulu burada başarısız olur. Böylece bazı kalıntıların neden yaşayıp bazılarının neden budandığı açıkça görülür.
C++, Python ve Java uygulamalarının tümü aynı akışı izler. Önce \(L\), \(n\)'e kadar olan en büyük asal kuvvetlerin çarpımı olarak dolaylı biçimde hesaplanır. Aynı asal kuvvetler, kalıntı sınıflarını inşa ederken kullanılan kademeli modülleri de belirler.
Daha sonra her bölen hedefi \(d\), her \(m\mid d\) böleni ve her \(r\bmod m\) kalıntısı için,
$$o+r \equiv 0 \pmod m$$
koşulunu sağlayan \(o\in\{0,\dots,n-1\}\) ofsetlerinin bit maskesi önceden hesaplanır. Bu önbellek sayesinde \(c \pmod M\) kalıntı sınıfı test edilirken, izinli ofset maskeleri yalnızca \(\gcd(M,d)\) ve \(c \bmod \gcd(M,d)\) kullanılarak anında oluşturulur.
Her kademeli modülde uygulama, yaşayan her \(c\) kalıntısını bir sonraki asal kuvvet altında tüm \(c+kM\) uzantılarına genişletir. Her uzantı bölenler ile ofsetler arasında bir iki parçalı grafik üretir. Grafik bit maskeleri olarak tutulur, bölen tarafı en kısıtlı maskelerden en serbest olanlara doğru işlenir ve standart bir artırıcı-yol eşleyicisi tam eşleme olup olmadığını kontrol eder.
Son modül \(L\)'ye ulaştığında elde kalan kalıntılar, tek periyot içindeki gerçek başlangıçlardır. Bunlar sıralanarak \(r_1,\dots,r_P\) elde edilir ve yukarıdaki periyodik formül istenen \(k\). başlangıcı verir. Problem 896 için uygulamalar bunu \(n=36\) ve \(k=36\) ile değerlendirir.
\(n\) aralık uzunluğu ve \(R\) de asal kuvvet aşamalarının tamamında incelenen toplam kalıntı sınıfı sayısı olsun. Asal listesi ile \(n\)'e kadarki en büyük asal kuvvetleri hesaplamak \(O(n\log\log n)\) zaman ve \(O(n)\) bellek gerektirir.
Maske önbelleğinin kurulumu
$$\sum_{d=1}^{n}\sum_{m\mid d} O(mn)$$
zaman alır; çünkü her \((d,m)\) çifti için modulo \(m\)'deki tüm kalıntılar bütün \(n\) ofset üzerinden genişletilir. Genel \(n\) için bu en kötü durumda \(O(n^3)\) olur, ancak burada \(n=36\) küçük ve sabittir. Depolama maliyeti ise
$$\sum_{d=1}^{n}\sum_{m\mid d} O(m)$$
kadardır ve pratikte karesel ölçektedir.
Her kalıntı testi \(n\) maske kurar ve \(n\times n\) grafikte DFS tabanlı bir iki parçalı eşleme çalıştırır; bu da aday başına en kötü durumda \(O(n^3)\) zaman verir. Toplam arama maliyeti \(O(Rn^3)\) olur. Erken modüler aşamalardaki güçlü budama sayesinde \(R\) yönetilebilir kalır. Bu yüzden kaba kuvvet araması umutsuzken bu yöntem pratiktir.
Para una longitud fija \(n\), llamemos divisible al intervalo \([a,a+n-1]\) si sus \(n\) términos pueden reordenarse de modo que el \(k\)-ésimo término elegido sea divisible por \(k\) para todo \(1\le k\le n\). El Problema 896 pide el valor inicial \(a\) número \(36\) cuando \(n=36\).
De forma equivalente, necesitamos desplazamientos distintos \(o_1,\dots,o_n\in\{0,\dots,n-1\}\) tales que
$$a+o_d \equiv 0 \pmod d \qquad (1\le d\le n).$$
Las implementaciones no recorren los intervalos uno por uno. En su lugar, convierten cada intervalo en un problema de emparejamiento bipartito y aprovechan que toda la condición es periódica módulo \(\operatorname{lcm}(1,2,\dots,n)\).
La observación central es que el problema no depende de los tamaños absolutos de los números, sino de qué residuos de divisibilidad aparecen dentro de un bloque de longitud \(n\). Una vez escrita esa condición como un problema de emparejamiento, la periodicidad y la descomposición en potencias primas reducen la búsqueda a un cálculo finito y manejable.
Para un valor inicial \(a\), definimos un grafo bipartito con lado izquierdo \(D=\{1,2,\dots,n\}\) y lado derecho \(O=\{0,1,\dots,n-1\}\). Conectamos el divisor \(d\) con el desplazamiento \(o\) cuando
$$a+o \equiv 0 \pmod d.$$
Un emparejamiento perfecto en este grafo elige una posición distinta del intervalo para cada divisor \(d\). Por lo tanto, \([a,a+n-1]\) es divisible si y solo si este grafo tiene un emparejamiento perfecto. El criterio teórico de existencia es el teorema matrimonial de Hall, y las implementaciones lo comprueban algorítmicamente mediante caminos aumentantes.
Para cada \(d\) fijo, la relación de adyacencia depende solo de \(a \bmod d\). Así, todo el grafo depende solo de \(a \bmod L\), donde
$$L=\operatorname{lcm}(1,2,\dots,n)=\prod_{p\le n} p^{\lfloor \log_p n\rfloor}.$$
En consecuencia, si \(a\) funciona, entonces \(a+L\) también funciona. Si escribimos los inicios válidos dentro de un período como
$$1\le r_1\lt r_2\lt \dots\lt r_P\le L,$$
la sucesión infinita completa es periódica:
$$a_k=\left\lfloor\frac{k-1}{P}\right\rfloor L+r_{1+((k-1)\bmod P)}.$$
Por tanto, el problema se reduce a enumerar las clases residuales válidas dentro de un único período.
En vez de comprobar todas las clases residuales módulo \(L\) de una sola vez, las implementaciones las construyen de forma incremental. Escribimos \(L\) como producto de máximas potencias primas coprimas entre sí:
$$L=\prod_{p\le n} q_p,\qquad q_p=p^{\lfloor \log_p n\rfloor}.$$
Después de procesar algunos de esos factores, sea \(M\) su producto y supongamos que solo conocemos \(a\equiv c \pmod M\). Para un divisor \(d\), la parte ya fijada de la condición de divisibilidad es exactamente
$$\delta_M(d)=\gcd(M,d).$$
En efecto, \(\delta_M(d)\) conserva precisamente las potencias primas de \(d\) que ya están presentes en \(M\). Entonces un desplazamiento \(o\) sigue siendo compatible con la clase residual \(c \bmod M\) cuando
$$c+o \equiv 0 \pmod{\delta_M(d)}.$$
Esto produce un problema de emparejamiento relajado: obliga a cumplir todas las potencias primas ya procesadas y deja las restantes para más adelante. Toda solución exacta sobrevive a todas las etapas relajadas, y cuando \(M=L\) el problema relajado coincide con el original.
Sea \(q\) la siguiente potencia prima, de modo que el nuevo módulo es \(Mq\). Como \(\gcd(M,q)=1\), toda extensión de \(c \pmod M\) a módulo \(Mq\) tiene la forma
$$c+kM \qquad (0\le k\lt q).$$
Cada candidato se prueba construyendo el grafo relajado con condiciones de divisibilidad módulo \(\gcd(Mq,d)\). Si ese grafo relajado no tiene emparejamiento perfecto, la clase residual no puede conducir a una residual completa válida y se descarta de inmediato.
Este proceso de ramificación y poda es mucho menor que recorrer por fuerza bruta todas las \(L\) residuales. En la etapa final, los supervivientes son exactamente los inicios válidos de un período.
Tomemos \(n=4\). Entonces \(L=\operatorname{lcm}(1,2,3,4)=12\). Consideremos el intervalo que empieza en \(a=6\), es decir, \(\{6,7,8,9\}\). Los desplazamientos permitidos son
$$\begin{aligned} d=1&:& \{0,1,2,3\},\\ d=2&:& \{0,2\},\\ d=3&:& \{0,3\},\\ d=4&:& \{2\}. \end{aligned}$$
Existe un emparejamiento perfecto: el divisor \(4\) debe usar el desplazamiento \(2\) (el número \(8\)), el divisor \(3\) puede usar el desplazamiento \(3\) (el número \(9\)), el divisor \(2\) usa entonces el desplazamiento \(0\) (el número \(6\)) y el divisor \(1\) toma el desplazamiento restante \(1\) (el número \(7\)). Por lo tanto, \(a=6\) es un inicio válido.
En cambio, para \(a=5\) el intervalo es \(\{5,6,7,8\}\) y los desplazamientos críticos son
$$d=2:\{1,3\},\qquad d=3:\{1\},\qquad d=4:\{3\}.$$
Los divisores \(2,3,4\) solo pueden usar conjuntamente los dos desplazamientos \(\{1,3\}\), así que falla la condición de Hall. Eso muestra exactamente por qué algunas residuales sobreviven en la búsqueda periódica y otras se eliminan.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero calculan \(L\) de forma indirecta como el producto de las máximas potencias primas hasta \(n\). Esas mismas potencias primas definen los módulos intermedios usados durante la construcción de residuales.
Después precalculan, para cada divisor objetivo \(d\), cada divisor \(m\mid d\) y cada residuo \(r\bmod m\), la máscara de bits de los desplazamientos \(o\in\{0,\dots,n-1\}\) que cumplen
$$o+r \equiv 0 \pmod m.$$
Gracias a esa caché, cuando se prueba una clase residual \(c \pmod M\), la implementación puede ensamblar inmediatamente todas las máscaras permitidas a partir de \(\gcd(M,d)\) y de \(c \bmod \gcd(M,d)\).
En cada módulo intermedio, la implementación extiende cada residual superviviente \(c\) a todos los valores \(c+kM\) bajo la siguiente potencia prima. Cada extensión genera un grafo bipartito entre divisores y desplazamientos. El grafo se representa con máscaras de bits, el lado de los divisores se procesa desde las máscaras más restrictivas hasta las menos restrictivas y un emparejador estándar por caminos aumentantes decide si existe un emparejamiento perfecto.
Una vez que el último módulo alcanza \(L\), las residuales supervivientes son exactamente los inicios válidos dentro de un período. Al ordenarlas obtenemos \(r_1,\dots,r_P\), y la fórmula periódica anterior devuelve el \(k\)-ésimo inicio pedido. En el Problema 896 las implementaciones evalúan esto con \(n=36\) y \(k=36\).
Sea \(n\) la longitud del intervalo y \(R\) el número total de clases residuales examinadas a lo largo de todas las etapas del refinamiento por potencias primas. Calcular la lista de primos y las máximas potencias primas hasta \(n\) cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria.
La construcción de la caché de máscaras requiere
$$\sum_{d=1}^{n}\sum_{m\mid d} O(mn)$$
de tiempo, porque para cada par \((d,m)\) se expanden todas las clases residuales módulo \(m\) sobre los \(n\) desplazamientos. En el peor caso, para un \(n\) genérico esto es \(O(n^3)\), aunque aquí \(n=36\) es pequeño y fijo. El almacenamiento es
$$\sum_{d=1}^{n}\sum_{m\mid d} O(m),$$
lo que en la práctica queda en escala cuadrática.
Cada prueba de una residual construye \(n\) máscaras y ejecuta un emparejamiento bipartito basado en DFS sobre un grafo \(n\times n\), con coste \(O(n^3)\) en el peor caso por candidato. En total, la búsqueda cuesta \(O(Rn^3)\), y \(R\) se mantiene razonable gracias a la poda fuerte en las primeras etapas modulares. Por eso el método es viable aunque un barrido ingenuo de todos los intervalos no lo sea.
对固定长度 \(n\)，如果区间 \([a,a+n-1]\) 中的 \(n\) 个整数可以重新排列，使得重新排列后的第 \(k\) 个数都能被 \(k\) 整除，其中 \(1\le k\le n\)，那么称这个区间是可整除区间。第 896 题要求在 \(n=36\) 时，求第 \(36\) 个这样的起点 \(a\)。
等价地说，我们需要在 \(\{0,\dots,n-1\}\) 中找到互不相同的偏移量 \(o_1,\dots,o_n\)，满足
$$a+o_d \equiv 0 \pmod d \qquad (1\le d\le n).$$
实现并没有逐个扫描区间，而是把每个区间转写成一个二分图完美匹配问题，再利用整个条件对 \(\operatorname{lcm}(1,2,\dots,n)\) 取模时具有周期性这一事实。
核心观察是：这个问题真正关心的不是区间内数字的绝对大小，而是长度为 \(n\) 的连续块里出现了哪些可整除余数模式。一旦把条件写成匹配问题，周期性和素数幂分解就可以把原本看似无限的搜索缩减成一个有限且可控的计算。
对起点 \(a\)，构造一个二分图。左侧顶点集合为 \(D=\{1,2,\dots,n\}\)，右侧顶点集合为 \(O=\{0,1,\dots,n-1\}\)。当且仅当
$$a+o \equiv 0 \pmod d$$
时，在除数 \(d\) 与偏移量 \(o\) 之间连边。这个图中的完美匹配，恰好表示为每个除数 \(d\) 选择了区间中的一个互不重复的位置。因此，\([a,a+n-1]\) 是可整除区间，当且仅当该图存在完美匹配。理论上的存在性判据是 Hall 婚配定理，而实现使用增广路算法来进行实际判定。
对固定的 \(d\)，是否连边只取决于 \(a \bmod d\)。因此整个二分图只取决于 \(a \bmod L\)，其中
$$L=\operatorname{lcm}(1,2,\dots,n)=\prod_{p\le n} p^{\lfloor \log_p n\rfloor}.$$
于是如果 \(a\) 可行，那么 \(a+L\) 也必然可行。设一个周期内所有合法起点按从小到大排列为
$$1\le r_1\lt r_2\lt \dots\lt r_P\le L,$$
那么全部可整除区间起点构成一条周期序列：
$$a_k=\left\lfloor\frac{k-1}{P}\right\rfloor L+r_{1+((k-1)\bmod P)}.$$
所以题目实质上只需要求出一个周期内哪些余数类有效。
实现并不是一次性检查模 \(L\) 的全部余数，而是逐步构造。把 \(L\) 写成若干两两互素的最大素数幂之积：
$$L=\prod_{p\le n} q_p,\qquad q_p=p^{\lfloor \log_p n\rfloor}.$$
假设目前已经处理了一部分这样的因子，它们的乘积为 \(M\)，并且我们只知道 \(a\equiv c \pmod M\)。对于某个除数 \(d\)，已经确定下来的那部分整除信息正好是
$$\delta_M(d)=\gcd(M,d).$$
这是因为 \(\delta_M(d)\) 恰好保留了 \(d\) 中已经出现在 \(M\) 里的那些素数幂。因此，当
$$c+o \equiv 0 \pmod{\delta_M(d)}$$
成立时，偏移量 \(o\) 就仍然与余数类 \(c \bmod M\) 相容。这样我们得到一个“放松版”的匹配问题：它强制满足已经处理过的素数幂条件，而把剩下的部分留到后面处理。任何真正的精确解都会通过所有这些中间阶段；当 \(M=L\) 时，这个放松问题就与原问题完全一致。
设下一项素数幂因子为 \(q\)，新模数就是 \(Mq\)。由于 \(\gcd(M,q)=1\)，从 \(c \pmod M\) 扩展到模 \(Mq\) 的所有余数类都可以写成
$$c+kM \qquad (0\le k\lt q).$$
对每一个候选余数，都构造一个放松图，其中除数 \(d\) 的约束只检查到 \(\gcd(Mq,d)\) 这一层。如果这个放松图已经不存在完美匹配，那么该余数类无论如何也不可能延伸成最终的合法余数，于是可以立刻丢弃。
这种“分支加剪枝”的过程，远比直接暴力枚举模 \(L\) 的全部余数要小得多。等到最后一层处理完，剩下的正好就是单个周期中的全部合法起点。
取 \(n=4\)。此时 \(L=\operatorname{lcm}(1,2,3,4)=12\)。考虑起点 \(a=6\) 的区间，也就是 \(\{6,7,8,9\}\)。对应的允许偏移量集合为
$$\begin{aligned} d=1&:& \{0,1,2,3\},\\ d=2&:& \{0,2\},\\ d=3&:& \{0,3\},\\ d=4&:& \{2\}. \end{aligned}$$
这个图存在完美匹配：除数 \(4\) 只能取偏移量 \(2\)（也就是数字 \(8\)），除数 \(3\) 可以取偏移量 \(3\)（数字 \(9\)），除数 \(2\) 于是取偏移量 \(0\)（数字 \(6\)），最后除数 \(1\) 取剩下的偏移量 \(1\)（数字 \(7\)）。所以 \(a=6\) 是一个合法起点。
相反，当 \(a=5\) 时，区间是 \(\{5,6,7,8\}\)，关键的偏移量集合变成
$$d=2:\{1,3\},\qquad d=3:\{1\},\qquad d=4:\{3\}.$$
此时除数 \(2,3,4\) 合起来只能占用两个偏移量 \(\{1,3\}\)，因此 Hall 条件失败。这个例子清楚地说明了为什么有些余数类会在周期搜索中保留下来，而另一些会被及时剪掉。
C++、Python 和 Java 的实现遵循完全相同的流程。首先，它们把 \(L\) 间接计算为不超过 \(n\) 的所有最大素数幂之积。这些素数幂同时也定义了逐层扩展余数时使用的模数序列。
接着，它们对每个目标除数 \(d\)、每个满足 \(m\mid d\) 的约数 \(m\)、以及每个余数 \(r\bmod m\)，预先计算出满足
$$o+r \equiv 0 \pmod m$$
的偏移量 \(o\in\{0,\dots,n-1\}\) 所对应的位掩码。这样在测试某个余数类 \(c \pmod M\) 时，实现只需利用 \(\gcd(M,d)\) 和 \(c \bmod \gcd(M,d)\)，就能立刻拼出所有允许偏移量的掩码。
在每一个中间模数阶段，实现把所有仍然存活的余数 \(c\) 扩展成下一层的全部 \(c+kM\)。每个扩展都会得到一个“除数对偏移量”的二分图。这个图用位掩码表示，除数一侧按照可选偏移量数量从少到多排序，然后用标准的增广路匹配来判断是否存在完美匹配。
最后，当模数达到 \(L\) 时，所有幸存的余数类就是单个周期中的精确合法起点。把它们排序后得到 \(r_1,\dots,r_P\)，再代入上面的周期公式，就能得到所需的第 \(k\) 个起点。对第 896 题来说，实现使用的是 \(n=36\) 和 \(k=36\)。
设 \(n\) 是区间长度，\(R\) 是在整个素数幂细化过程中总共检查的余数类数量。生成素数列表以及不超过 \(n\) 的最大素数幂需要 \(O(n\log\log n)\) 时间和 \(O(n)\) 空间。
位掩码缓存的构建时间为
$$\sum_{d=1}^{n}\sum_{m\mid d} O(mn),$$
因为对每个 \((d,m)\) 对，都要把模 \(m\) 的每个余数在全部 \(n\) 个偏移量上展开一次。对一般 \(n\) 而言，这个量最坏可视为 \(O(n^3)\)，但本题中 \(n=36\) 很小且固定。缓存的存储量为
$$\sum_{d=1}^{n}\sum_{m\mid d} O(m),$$
在实际规模下接近二次增长。
每次测试一个候选余数类时，都要构造 \(n\) 个掩码，并在一个 \(n\times n\) 的二分图上运行基于 DFS 的匹配算法，因此单次候选测试的最坏时间是 \(O(n^3)\)。总搜索代价因此为 \(O(Rn^3)\)。由于前几层模数阶段就能进行强力剪枝，\(R\) 会被控制在可处理的范围内。这正是该方法可行，而朴素逐区间扫描不可行的原因。
Для фиксированной длины \(n\) назовем интервал \([a,a+n-1]\) делимым, если его \(n\) чисел можно переставить так, чтобы \(k\)-е выбранное число делилось на \(k\) для каждого \(1\le k\le n\). В задаче 896 требуется найти \(36\)-е такое начальное значение \(a\) при \(n=36\).
Эквивалентно, нужно выбрать попарно различные смещения \(o_1,\dots,o_n\in\{0,\dots,n-1\}\), удовлетворяющие
$$a+o_d \equiv 0 \pmod d \qquad (1\le d\le n).$$
Реализации не перебирают интервалы по одному. Вместо этого каждый интервал переводится в задачу о совершенном паросочетании в двудольном графе, а затем используется факт, что все условие периодично по модулю \(\operatorname{lcm}(1,2,\dots,n)\).
Главное наблюдение состоит в том, что задача зависит не от абсолютных величин чисел, а только от того, какие шаблоны делимости встречаются внутри одного блока длины \(n\). Как только это записано как задача о паросочетании, периодичность и разложение по простым степеням сводят поиск к конечному и управляемому вычислению.
Для заданного старта \(a\) построим двудольный граф: левая доля \(D=\{1,2,\dots,n\}\), правая доля \(O=\{0,1,\dots,n-1\}\). Ребро между делителем \(d\) и смещением \(o\) проводится тогда и только тогда, когда
$$a+o \equiv 0 \pmod d.$$
Совершенное паросочетание в таком графе выбирает для каждого делителя \(d\) свою собственную позицию внутри интервала. Поэтому \([a,a+n-1]\) делим тогда и только тогда, когда граф имеет совершенное паросочетание. Теоретическим критерием служит теорема Холла, а реализации проверяют это условие алгоритмически при помощи увеличивающих путей.
Для фиксированного \(d\) наличие ребра зависит только от \(a \bmod d\). Значит, весь граф зависит только от \(a \bmod L\), где
$$L=\operatorname{lcm}(1,2,\dots,n)=\prod_{p\le n} p^{\lfloor \log_p n\rfloor}.$$
Следовательно, если работает \(a\), то работает и \(a+L\). Пусть все корректные старты внутри одного периода записаны как
$$1\le r_1\lt r_2\lt \dots\lt r_P\le L.$$
Тогда вся бесконечная последовательность стартов периодична:
$$a_k=\left\lfloor\frac{k-1}{P}\right\rfloor L+r_{1+((k-1)\bmod P)}.$$
Значит, задача сводится к перечислению допустимых классов вычетов внутри одного периода.
Вместо проверки всех вычетов по модулю \(L\) сразу реализации строят их постепенно. Запишем \(L\) как произведение попарно взаимно простых максимальных степеней простых чисел:
$$L=\prod_{p\le n} q_p,\qquad q_p=p^{\lfloor \log_p n\rfloor}.$$
После обработки части этих множителей пусть их произведение равно \(M\), и мы знаем только, что \(a\equiv c \pmod M\). Для делителя \(d\) уже зафиксированная часть условия делимости равна
$$\delta_M(d)=\gcd(M,d).$$
Действительно, \(\delta_M(d)\) сохраняет ровно те простые степени из \(d\), которые уже присутствуют в \(M\). Поэтому смещение \(o\) остается совместимым с классом вычетов \(c \bmod M\), когда
$$c+o \equiv 0 \pmod{\delta_M(d)}.$$
Так возникает ослабленная задача о паросочетании: она навязывает все уже обработанные простые степени и откладывает остальные на более поздние шаги. Любое точное решение переживает все ослабленные этапы, а при \(M=L\) ослабленная задача совпадает с исходной.
Пусть следующая простая степень равна \(q\), тогда новый модуль равен \(Mq\). Поскольку \(\gcd(M,q)=1\), каждое продолжение класса \(c \pmod M\) до модуля \(Mq\) имеет вид
$$c+kM \qquad (0\le k\lt q).$$
Каждый кандидат проверяется построением ослабленного графа, в котором для делителя \(d\) используется модуль \(\gcd(Mq,d)\). Если в таком графе уже нет совершенного паросочетания, этот класс вычетов никогда не приведет к точному допустимому вычету и может быть немедленно отброшен.
Такое ветвление с отсечением намного меньше полного перебора всех \(L\) вычетов. На последнем шаге остаются ровно те классы, которые и являются корректными стартами в пределах одного периода.
Возьмем \(n=4\). Тогда \(L=\operatorname{lcm}(1,2,3,4)=12\). Рассмотрим интервал с началом \(a=6\), то есть \(\{6,7,8,9\}\). Допустимые смещения равны
$$\begin{aligned} d=1&:& \{0,1,2,3\},\\ d=2&:& \{0,2\},\\ d=3&:& \{0,3\},\\ d=4&:& \{2\}. \end{aligned}$$
Совершенное паросочетание существует: делитель \(4\) обязан взять смещение \(2\) (число \(8\)), делитель \(3\) может взять смещение \(3\) (число \(9\)), делитель \(2\) после этого берет смещение \(0\) (число \(6\)), а делитель \(1\) получает оставшееся смещение \(1\) (число \(7\)). Значит, \(a=6\) является допустимым стартом.
Для \(a=5\) интервал равен \(\{5,6,7,8\}\), и критические множества смещений таковы:
$$d=2:\{1,3\},\qquad d=3:\{1\},\qquad d=4:\{3\}.$$
Делители \(2,3,4\) вместе могут использовать только два смещения \(\{1,3\}\), поэтому условие Холла нарушается. Этот пример хорошо показывает, почему некоторые классы вычетов проходят периодический поиск, а другие отсеиваются сразу.
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала \(L\) вычисляется косвенно как произведение максимальных степеней простых чисел, не превосходящих \(n\). Эти же степени простых определяют последовательность промежуточных модулей при построении классов вычетов.
Затем для каждого целевого делителя \(d\), каждого делителя \(m\mid d\) и каждого остатка \(r\bmod m\) заранее строится битовая маска смещений \(o\in\{0,\dots,n-1\}\), удовлетворяющих
$$o+r \equiv 0 \pmod m.$$
Благодаря этому кэшу, когда проверяется класс вычетов \(c \pmod M\), все допустимые маски смещений можно мгновенно собрать из \(\gcd(M,d)\) и значения \(c \bmod \gcd(M,d)\).
На каждом промежуточном модуле реализация расширяет каждый выживший класс \(c\) до всех значений \(c+kM\) под следующей простой степенью. Каждое расширение задает двудольный граф между делителями и смещениями. Граф хранится в виде битовых масок, вершины-делители обрабатываются от самых ограниченных масок к наименее ограниченным, а стандартный алгоритм увеличивающих путей проверяет существование совершенного паросочетания.
Когда последний модуль становится равным \(L\), оставшиеся классы вычетов и есть точные допустимые старты в пределах одного периода. После сортировки получаем \(r_1,\dots,r_P\), а периодическая формула выше возвращает нужный \(k\)-й старт. В задаче 896 реализации подставляют \(n=36\) и \(k=36\).
Пусть \(n\) обозначает длину интервала, а \(R\) - общее число классов вычетов, проверенных на всех этапах уточнения по простым степеням. Построение списка простых чисел и максимальных степеней простых до \(n\) занимает \(O(n\log\log n)\) времени и \(O(n)\) памяти.
Построение кэша масок требует
$$\sum_{d=1}^{n}\sum_{m\mid d} O(mn)$$
времени, потому что для каждой пары \((d,m)\) каждый класс вычетов по модулю \(m\) разворачивается по всем \(n\) смещениям. В худшем случае для общего \(n\) это дает \(O(n^3)\), хотя здесь \(n=36\) мало и фиксировано. Объем хранения равен
$$\sum_{d=1}^{n}\sum_{m\mid d} O(m),$$
что на практике имеет квадратичный масштаб.
Каждая проверка кандидата строит \(n\) масок и запускает двудольное паросочетание на графе \(n\times n\) с DFS-поиском, то есть дает \(O(n^3)\) в худшем случае на один кандидат. Итого полный поиск стоит \(O(Rn^3)\). Благодаря сильной отсечке на ранних модульных этапах величина \(R\) остается приемлемой. Именно поэтому метод работает, тогда как наивный перебор всех интервалов был бы бесперспективен.
لعدد ثابت من الحدود \(n\)، نسمي الفترة \([a,a+n-1]\) فترة قابلة للقسمة إذا أمكن إعادة ترتيب عناصرها \(n\) بحيث يكون العنصر المختار في الموضع \(k\) قابلاً للقسمة على \(k\) لكل \(1\le k\le n\). تطلب المسألة 896 إيجاد قيمة البداية \(a\) رقم \(36\) عندما يكون \(n=36\).
وبصياغة مكافئة، نحتاج إلى إزاحات مختلفة \(o_1,\dots,o_n\in\{0,\dots,n-1\}\) تحقق
$$a+o_d \equiv 0 \pmod d \qquad (1\le d\le n).$$
التنفيذات لا تفحص الفترات واحدة واحدة. بدلاً من ذلك تحوّل كل فترة إلى مسألة مطابقة كاملة في رسم ثنائي، ثم تستفيد من أن الشرط كله دوري modulo \(\operatorname{lcm}(1,2,\dots,n)\).
الفكرة المركزية هي أن المسألة لا تعتمد على القيم المطلقة للأعداد داخل الفترة، بل على نمط بواقي القابلية للقسمة الذي يظهر داخل كتلة طولها \(n\). وعندما نعيد كتابة الشرط بهذه الصورة، تصبح الدورية وتحليل القوى الأولية هما الأداتين اللتين تختصران البحث إلى حساب منتهٍ وممكن التنفيذ.
لقيمة بداية \(a\)، نعرّف رسماً بيانياً ثنائياً: الجهة اليسرى هي \(D=\{1,2,\dots,n\}\) والجهة اليمنى هي \(O=\{0,1,\dots,n-1\}\). نصل بين المقسوم عليه \(d\) والإزاحة \(o\) إذا وفقط إذا كان
$$a+o \equiv 0 \pmod d.$$
وجود مطابقة كاملة في هذا الرسم يعني اختيار موضع مختلف داخل الفترة لكل مقسوم عليه \(d\). لذلك تكون \([a,a+n-1]\) فترة قابلة للقسمة إذا وفقط إذا كان هذا الرسم يحتوي على مطابقة كاملة. المعيار النظري للوجود هو مبرهنة هول للزواج، أما التنفيذات فتفحص الشرط خوارزمياً بواسطة المسارات المُعزِّزة.
لأي \(d\) ثابت، تعتمد علاقة الحواف فقط على \(a \bmod d\). ومن ثم فإن الرسم كله يعتمد فقط على \(a \bmod L\)، حيث
$$L=\operatorname{lcm}(1,2,\dots,n)=\prod_{p\le n} p^{\lfloor \log_p n\rfloor}.$$
إذن إذا كانت القيمة \(a\) صالحة، فالقيمة \(a+L\) صالحة أيضاً. وإذا رمزنا إلى بدايات الفترات الصالحة داخل دورة واحدة بالترتيب
$$1\le r_1\lt r_2\lt \dots\lt r_P\le L,$$
فإن المتتالية اللانهائية الكاملة للبدايات تكون دورية:
$$a_k=\left\lfloor\frac{k-1}{P}\right\rfloor L+r_{1+((k-1)\bmod P)}.$$
وبذلك تختزل المسألة إلى إيجاد فئات البواقي الصالحة داخل دورة واحدة فقط.
بدلاً من فحص جميع البواقي modulo \(L\) دفعةً واحدة، تبنيها التنفيذات تدريجياً. نكتب \(L\) على صورة حاصل ضرب أكبر القوى الأولية المتباينة أولياً اثنين اثنين:
$$L=\prod_{p\le n} q_p,\qquad q_p=p^{\lfloor \log_p n\rfloor}.$$
بعد معالجة بعض هذه العوامل، ليكن \(M\) هو حاصل ضربها، ولنفرض أننا لا نعرف إلا أن \(a\equiv c \pmod M\). عندئذ فإن الجزء الذي تم تثبيته بالفعل من شرط القسمة على \(d\) هو
$$\delta_M(d)=\gcd(M,d).$$
وذلك لأن \(\delta_M(d)\) تحتفظ بالضبط بالقوى الأولية الموجودة في \(d\) والتي أصبحت موجودة مسبقاً داخل \(M\). لذا تبقى الإزاحة \(o\) منسجمة مع فئة الباقي \(c \bmod M\) عندما يتحقق
$$c+o \equiv 0 \pmod{\delta_M(d)}.$$
وهكذا نحصل على مسألة مطابقة مُرخّصة: فهي تفرض جميع القيود الناتجة عن القوى الأولية التي عولجت بالفعل، وتؤجل الباقي إلى المراحل التالية. أي حل دقيق حقيقي ينجو من كل هذه المراحل، وعندما يصبح \(M=L\) تتطابق المسألة المُرخّصة مع المسألة الأصلية تماماً.
إذا كانت القوة الأولية التالية هي \(q\)، فإن المودول الجديد هو \(Mq\). وبما أن \(\gcd(M,q)=1\)، فإن كل امتداد لفئة \(c \pmod M\) إلى modulo \(Mq\) يأخذ الشكل
$$c+kM \qquad (0\le k\lt q).$$
يُختبر كل مرشح ببناء الرسم المُرخّص الذي تُفحص فيه شروط القسمة على \(d\) حتى modulo \(\gcd(Mq,d)\) فقط. فإذا كان هذا الرسم المُرخّص لا يملك مطابقة كاملة، فإن تلك الفئة لا يمكن أن تمتد أبداً إلى باقٍ نهائي صالح، ولذلك تُستبعد فوراً.
هذا الأسلوب القائم على التفرع مع الحذف أصغر بكثير من الفحص الشامل لكل البواقي modulo \(L\). وفي المرحلة الأخيرة تكون البواقي المتبقية هي بالضبط بدايات الفترات الصالحة داخل دورة واحدة.
لنأخذ \(n=4\). عندئذ يكون \(L=\operatorname{lcm}(1,2,3,4)=12\). انظر إلى الفترة التي تبدأ عند \(a=6\)، أي \(\{6,7,8,9\}\). مجموعات الإزاحات المسموح بها هي
$$\begin{aligned} d=1&:& \{0,1,2,3\},\\ d=2&:& \{0,2\},\\ d=3&:& \{0,3\},\\ d=4&:& \{2\}. \end{aligned}$$
توجد هنا مطابقة كاملة: المقسوم عليه \(4\) يجب أن يأخذ الإزاحة \(2\) (أي العدد \(8\))، والمقسوم عليه \(3\) يمكن أن يأخذ الإزاحة \(3\) (أي العدد \(9\))، ثم يأخذ المقسوم عليه \(2\) الإزاحة \(0\) (أي العدد \(6\))، ويأخذ المقسوم عليه \(1\) الإزاحة المتبقية \(1\) (أي العدد \(7\)). لذلك فإن \(a=6\) بداية صالحة.
أما عند \(a=5\) فتكون الفترة \(\{5,6,7,8\}\)، وتصبح الإزاحات الحرجة
$$d=2:\{1,3\},\qquad d=3:\{1\},\qquad d=4:\{3\}.$$
وبذلك لا تستطيع المقسومات \(2,3,4\) معاً استعمال إلا الإزاحتين \(\{1,3\}\)، فتفشل هنا قاعدة هول. يوضح هذا المثال تماماً لماذا تنجو بعض فئات البواقي أثناء البحث الدوري بينما تُقصى فئات أخرى مبكراً.
تتبع تنفيذات C++ وPython وJava المسار نفسه. أولاً تُحسب القيمة \(L\) بشكل غير مباشر بوصفها حاصل ضرب أكبر القوى الأولية التي لا تتجاوز \(n\). وهذه القوى نفسها تحدد أيضاً المودولات المرحلية المستخدمة أثناء بناء فئات البواقي.
بعد ذلك يُحسب مسبقاً، لكل مقسوم عليه هدف \(d\)، ولكل قاسم \(m\mid d\)، ولكل باقٍ \(r\bmod m\)، قناع البتات الخاص بالإزاحات \(o\in\{0,\dots,n-1\}\) التي تحقق
$$o+r \equiv 0 \pmod m.$$
هذا التخزين المسبق يعني أن التنفيذ، عند اختبار فئة باقٍ \(c \pmod M\)، يستطيع تكوين جميع أقنعة الإزاحات المسموح بها مباشرةً من \(\gcd(M,d)\) ومن \(c \bmod \gcd(M,d)\).
في كل مودول مرحلي، يوسّع التنفيذ كل باقٍ ناجٍ \(c\) إلى جميع القيم \(c+kM\) تحت القوة الأولية التالية. وكل امتداد يولد رسماً ثنائياً بين المقسومات والإزاحات. ويُمثَّل الرسم بأقنعة بتات، ثم تُعالَج جهة المقسومات من الأقنعة الأكثر تقييداً إلى الأقل تقييداً، وتُستخدم خوارزمية مطابقة معيارية تعتمد على المسارات المُعزِّزة للتحقق من وجود مطابقة كاملة.
عندما يصل آخر مودول إلى \(L\)، تكون فئات البواقي المتبقية هي البدايات الصحيحة تماماً داخل دورة واحدة. وبعد ترتيبها نحصل على \(r_1,\dots,r_P\)، ثم تعطي الصيغة الدورية السابقة قيمة البداية رقم \(k\) المطلوبة. وفي المسألة 896 تُقيَّم هذه الخطوات عند \(n=36\) و\(k=36\).
ليكن \(n\) طول الفترة، ولتكن \(R\) هي القيمة الكلية لعدد فئات البواقي التي تُفحص عبر جميع مراحل التنقية بالقوى الأولية. إن توليد قائمة الأعداد الأولية وأكبر القوى الأولية حتى \(n\) يكلف \(O(n\log\log n)\) زمناً و\(O(n)\) ذاكرة.
أما بناء ذاكرة أقنعة الإزاحات فيحتاج إلى
$$\sum_{d=1}^{n}\sum_{m\mid d} O(mn)$$
من الزمن، لأن كل زوج \((d,m)\) يقتضي توسيع كل فئة باقٍ modulo \(m\) عبر جميع الإزاحات \(n\). وفي أسوأ الأحوال يكون ذلك \(O(n^3)\) عندما نعامل \(n\) كمتحول عام، لكن هنا \(n=36\) صغير وثابت. أما التخزين فيساوي
$$\sum_{d=1}^{n}\sum_{m\mid d} O(m),$$
وهو عملياً من رتبة تربيعية.
كل اختبار لمرشح واحد يبني \(n\) أقنعة ثم يشغّل مطابقة ثنائية معتمدة على DFS على رسم \(n\times n\)، ولذلك تكون كلفة المرشح الواحد \(O(n^3)\) في أسوأ حالة. ومن ثم فإن الكلفة الكلية للبحث هي \(O(Rn^3)\). وبفضل الحذف القوي في المراحل المعيارية المبكرة تبقى \(R\) ضمن حجم يمكن التعامل معه، ولهذا السبب تكون الطريقة عملية رغم أن الفحص الساذج لجميع الفترات غير عملي تماماً.