For each pair \(2\le n\le m\le 100\), the problem considers a rectangle with side lengths \(n^4\) and \(m^4\). Its cells are listed once in row-major order and once in column-major order, so the reindexing from one list to the other is a permutation of all \((nm)^4\) positions. For each pair, we must find the minimum number of swaps needed to realize that permutation, and then sum those values over all admissible pairs.
A direct cycle walk on the full permutation would be hopeless, because the rectangle for one pair already has \(Q=(nm)^4\) cells. The implementations succeed by turning the transpose permutation into modular multiplication and then counting cycles through divisors of \(Q-1\).
Let the rectangle have \(r=m^4\) rows and \(c=n^4\) columns. Define
$$Q=rc=(nm)^4,\qquad L=Q-1,\qquad \alpha=r=m^4.$$
The entire task becomes a problem about the cycle structure of one modular permutation.
Take a cell in row \(i\) and column \(j\), with \(0\le i\lt r\) and \(0\le j\lt c\). Its row-major index is
$$x=ic+j,$$
while its column-major index is
$$y=jr+i.$$
Now compute \(rx\):
$$rx=r(ic+j)=irc+rj=iQ+rj\equiv i+rj=y \pmod{Q-1}.$$
So for every index except the last one, the reindexing permutation satisfies
$$\pi(x)\equiv \alpha x \pmod L,\qquad 0\le x\lt L.$$
The missing index \(x=L=Q-1\) is an extra fixed point. Because
$$L=(nm)^4-1\equiv -1 \pmod m,$$
we have \(\gcd(\alpha,L)=1\), so multiplication by \(\alpha\) genuinely permutes the residues modulo \(L\).
If a permutation on \(Q\) elements has \(C\) cycles, then the minimum number of swaps needed to realize it is \(Q-C\), since a cycle of length \(t\) takes exactly \(t-1\) swaps. The problem is therefore reduced to counting cycles of \(\pi\).
For a residue \(x\in \mathbb{Z}/L\mathbb{Z}\), define
$$d=\frac{L}{\gcd(x,L)}.$$
This number \(d\) is the additive order of \(x\) in the cyclic group \(\mathbb{Z}/L\mathbb{Z}\). Multiplication by \(\alpha\) preserves \(\gcd(x,L)\), because \(\alpha\) is invertible modulo \(L\). Therefore it also preserves \(d\). The permutation splits into invariant layers, one layer for each divisor \(d\mid L\).
Exactly \(\varphi(d)\) residues have additive order \(d\): they are the generators of the unique subgroup of size \(d\) inside the cyclic group \(\mathbb{Z}/L\mathbb{Z}\).
Write
$$g=\gcd(x,L),\qquad x=gu,\qquad L=gd,$$
so that \(\gcd(u,d)=1\). Then the condition that \(x\) returns to itself after \(t\) steps is
$$\alpha^t x\equiv x \pmod L.$$
Substituting \(x=gu\) and \(L=gd\) gives
$$gd\mid g(\alpha^t-1)u\iff d\mid(\alpha^t-1)u.$$
Because \(u\) is invertible modulo \(d\), this is equivalent to
$$\alpha^t\equiv 1 \pmod d.$$
So every orbit in the layer indexed by \(d\) has length
$$\operatorname{ord}_d(\alpha),$$
the multiplicative order of \(\alpha\) modulo \(d\). Since the layer contains \(\varphi(d)\) elements, its number of cycles is
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.$$
Summing those contributions over all divisors of \(L\) gives the number of cycles inside the modular part:
$$C_L=\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)},$$
with the natural convention \(\operatorname{ord}_1(\alpha)=1\). This already counts the fixed point \(x=0\). The index \(x=L=Q-1\) contributes one more fixed point outside the modular residue set, so the full cycle count is
$$C=C_L+1.$$
Therefore the swap count for the pair \((n,m)\) is
$$\boxed{\text{swaps}=Q-1-\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.}$$
The actual problem uses fourth powers, but the same mechanism is already visible in a small ordinary rectangle with \(r=4\) and \(c=3\). Then
$$Q=12,\qquad L=11,\qquad \alpha=4,$$
so on \(0\le x\lt 11\) we have
$$\pi(x)\equiv 4x \pmod{11}.$$
The only divisors of \(11\) are \(1\) and \(11\), hence
$$C_{11}=1+\frac{\varphi(11)}{\operatorname{ord}_{11}(4)}=1+\frac{10}{5}=3.$$
Indeed, the residues split as
$$0,$$
$$1\to 4\to 5\to 9\to 3\to 1,$$
$$2\to 8\to 10\to 7\to 6\to 2,$$
and the twelfth position \(x=11\) is the extra fixed point. So the total cycle count is \(4\), and the minimum number of swaps is
$$12-4=8.$$
This is the same small check used by the implementations to confirm the formula.
Set \(s=nm\). Then
$$L=s^4-1=(s-1)(s+1)(s^2+1).$$
Because \(s\le 10^4\), the three factors \(s-1\), \(s+1\), and \(s^2+1\) are moderate-size integers. Factoring those three numbers is enough to recover the complete prime factorization of \(L\).
For each prime power \(p^k\mid L\), the order satisfies
$$\operatorname{ord}_{p^k}(\alpha)\mid \varphi(p^k)=p^{k-1}(p-1).$$
The exact order is obtained by starting from \(\varphi(p^k)\) and repeatedly removing prime factors whenever the modular test
$$\alpha^{\,\varphi(p^k)/q}\equiv 1 \pmod{p^k}$$
still holds.
If
$$d=\prod_i p_i^{e_i},$$
then multiplicativity and the Chinese remainder theorem give
$$\varphi(d)=\prod_i \varphi(p_i^{e_i}),\qquad \operatorname{ord}_d(\alpha)=\operatorname{lcm}_i\operatorname{ord}_{p_i^{e_i}}(\alpha).$$
So a depth-first enumeration of the exponent choices \(0\le e_i\le v_{p_i}(L)\) visits every divisor \(d\mid L\) and accumulates its cycle contribution exactly, without ever traversing the \(Q\) entries of the rectangle.
The C++, Python, and Java implementations follow the same number-theoretic pipeline.
A prime sieve is built once. For a given pair \((n,m)\), the implementation forms \(s=nm\), factors \(s-1\), \(s+1\), and \(s^2+1\), and merges those exponents into the factorization of \(L=s^4-1\). Because different pairs can share the same product \(s\), this factorization is cached and reused. Factorizations of numbers of the form \(p-1\) are also cached, because they are needed repeatedly when reducing \(\varphi(p^k)\) to the exact order \(\operatorname{ord}_{p^k}(\alpha)\).
For each prime power \(p^k\mid L\), the implementation precomputes \(\varphi(p^k)\) and \(\operatorname{ord}_{p^k}(\alpha)\). It then runs a divisor DFS: each recursion level chooses one exponent for one prime, multiplies the running totient contribution, updates the running order with an \(\operatorname{lcm}\), and descends to the next prime. At every leaf, the divisor contribution
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}$$
is added to the cycle total \(C_L\). The returned swap count is therefore \(Q-1-C_L\).
The outer loops sum this value over all \(2\le n\le m\le 100\). The implementations also compare the divisor formula against explicit cycle decompositions on small cases; for example, the ordinary \(3\times 4\) rectangle gives \(8\) swaps exactly, matching the theory above.
For one pair \((n,m)\), the algorithm never iterates over all \(Q=(nm)^4\) positions. Its work is concentrated in three places: factoring \(s-1\), \(s+1\), and \(s^2+1\); computing multiplicative orders on the relevant prime powers; and enumerating the \(\tau(L)\) divisors of \(L\) with a DFS over prime exponents. In practice that is far smaller than a brute-force cycle walk on the full transpose permutation.
Memory usage is modest. The main data are the prime list, the caches for repeated factorizations, and the prime-power tables for the current pair. The method is efficient precisely because it manipulates the factorization of \(L=(nm)^4-1\), not the \((nm)^4\) matrix entries themselves.
Für jedes Paar \(2\le n\le m\le 100\) betrachtet die Aufgabe ein Rechteck mit Seitenlängen \(n^4\) und \(m^4\). Seine Zellen werden einmal in Row-major-Reihenfolge und einmal in Column-major-Reihenfolge linearisiert; der Übergang zwischen beiden Nummerierungen ist also eine Permutation aller \((nm)^4\) Positionen. Für jedes Paar ist die minimale Anzahl von Vertauschungen gesucht, und diese Werte werden anschließend summiert.
Ein direkter Zyklusdurchlauf auf der ganzen Permutation wäre aussichtslos, weil schon ein einziges Paar \(Q=(nm)^4\) Positionen erzeugt. Die Lösung funktioniert nur deshalb, weil sich die Transpositionspermutation als modulare Multiplikation schreiben lässt und ihre Zykluszahl über Teiler von \(Q-1\) ausgedrückt werden kann.
Wir schreiben \(r=m^4\) für die Zeilenzahl und \(c=n^4\) für die Spaltenzahl. Setze
$$Q=rc=(nm)^4,\qquad L=Q-1,\qquad \alpha=r=m^4.$$
Dann ist die gesamte Aufgabe auf die Zyklusstruktur einer einzigen modularen Permutation reduziert.
Betrachte eine Zelle in Zeile \(i\) und Spalte \(j\) mit \(0\le i\lt r\) und \(0\le j\lt c\). Ihr Row-major-Index ist
$$x=ic+j,$$
ihr Column-major-Index ist
$$y=jr+i.$$
Nun berechnen wir \(rx\):
$$rx=r(ic+j)=irc+rj=iQ+rj\equiv i+rj=y \pmod{Q-1}.$$
Also gilt für alle Indizes außer dem letzten
$$\pi(x)\equiv \alpha x \pmod L,\qquad 0\le x\lt L.$$
Der fehlende Index \(x=L=Q-1\) ist ein zusätzlicher Fixpunkt. Weil
$$L=(nm)^4-1\equiv -1 \pmod m,$$
folgt \(\gcd(\alpha,L)=1\), und Multiplikation mit \(\alpha\) ist tatsächlich eine Permutation modulo \(L\).
Hat eine Permutation auf \(Q\) Elementen insgesamt \(C\) Zyklen, dann benötigt man genau \(Q-C\) Vertauschungen, weil ein Zyklus der Länge \(t\) genau \(t-1\) Vertauschungen braucht. Damit ist die Aufgabe zu einem reinen Zykluszählproblem geworden.
Für einen Rest \(x\in \mathbb{Z}/L\mathbb{Z}\) definieren wir
$$d=\frac{L}{\gcd(x,L)}.$$
Dieses \(d\) ist die additive Ordnung von \(x\) in der zyklischen Gruppe \(\mathbb{Z}/L\mathbb{Z}\). Da \(\alpha\) modulo \(L\) invertierbar ist, bleibt \(\gcd(x,L)\) unter Multiplikation mit \(\alpha\) erhalten, also auch \(d\). Die Permutation zerfällt daher in invariante Schichten, je eine für jeden Teiler \(d\mid L\).
Genau \(\varphi(d)\) Restklassen besitzen additive Ordnung \(d\): Es sind genau die Erzeuger der eindeutigen Untergruppe der Größe \(d\) in \(\mathbb{Z}/L\mathbb{Z}\).
Schreibe
$$g=\gcd(x,L),\qquad x=gu,\qquad L=gd,$$
wobei \(\gcd(u,d)=1\) gilt. Dass \(x\) nach \(t\) Schritten wieder auf sich selbst zurückkehrt, bedeutet
$$\alpha^t x\equiv x \pmod L.$$
Mit \(x=gu\) und \(L=gd\) wird daraus
$$gd\mid g(\alpha^t-1)u\iff d\mid(\alpha^t-1)u.$$
Weil \(u\) modulo \(d\) invertierbar ist, ist dies äquivalent zu
$$\alpha^t\equiv 1 \pmod d.$$
Somit hat jede Bahn in der Schicht zu \(d\) die Länge
$$\operatorname{ord}_d(\alpha),$$
also die multiplikative Ordnung von \(\alpha\) modulo \(d\). Da die Schicht \(\varphi(d)\) Elemente enthält, trägt sie
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}$$
Zyklen bei.
Die Summe über alle Teiler von \(L\) liefert die Zahl der Zyklen im modularen Teil:
$$C_L=\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)},$$
wobei \(\operatorname{ord}_1(\alpha)=1\) gesetzt wird. Darin ist der Fixpunkt \(x=0\) bereits enthalten. Der Index \(x=L=Q-1\) liefert einen weiteren Fixpunkt außerhalb der Restklassenmenge, also insgesamt
$$C=C_L+1.$$
Daraus folgt für das Paar \((n,m)\)
$$\boxed{\text{Vertauschungen}=Q-1-\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.}$$
Im eigentlichen Problem treten vierte Potenzen auf, aber der Mechanismus ist schon an einem kleinen gewöhnlichen Rechteck mit \(r=4\) und \(c=3\) sichtbar. Dann gilt
$$Q=12,\qquad L=11,\qquad \alpha=4,$$
also für \(0\le x\lt 11\)
$$\pi(x)\equiv 4x \pmod{11}.$$
Die einzigen Teiler von \(11\) sind \(1\) und \(11\), daher
$$C_{11}=1+\frac{\varphi(11)}{\operatorname{ord}_{11}(4)}=1+\frac{10}{5}=3.$$
Tatsächlich zerfallen die Reste in
$$0,$$
$$1\to 4\to 5\to 9\to 3\to 1,$$
$$2\to 8\to 10\to 7\to 6\to 2,$$
und die zwölfte Position \(x=11\) ist der zusätzliche Fixpunkt. Also gibt es insgesamt \(4\) Zyklen und damit
$$12-4=8$$
Vertauschungen. Genau diese kleine Kontrolle wird auch von den Implementierungen verwendet.
Setze \(s=nm\). Dann gilt
$$L=s^4-1=(s-1)(s+1)(s^2+1).$$
Da \(s\le 10^4\), sind \(s-1\), \(s+1\) und \(s^2+1\) nur mittelgroße Zahlen. Es genügt also, diese drei Faktoren zu zerlegen, um die vollständige Primfaktorzerlegung von \(L\) zu erhalten.
Für jede Primzahlpotenz \(p^k\mid L\) gilt
$$\operatorname{ord}_{p^k}(\alpha)\mid \varphi(p^k)=p^{k-1}(p-1).$$
Die exakte Ordnung erhält man, indem man mit \(\varphi(p^k)\) startet und Primfaktoren so lange herausdividiert, wie der modulare Test
$$\alpha^{\,\varphi(p^k)/q}\equiv 1 \pmod{p^k}$$
erfüllt bleibt.
Für
$$d=\prod_i p_i^{e_i}$$
liefern Multiplikativität und der chinesische Restsatz
$$\varphi(d)=\prod_i \varphi(p_i^{e_i}),\qquad \operatorname{ord}_d(\alpha)=\operatorname{lcm}_i\operatorname{ord}_{p_i^{e_i}}(\alpha).$$
Eine Tiefensuche über alle Exponenten \(0\le e_i\le v_{p_i}(L)\) besucht deshalb jeden Teiler \(d\mid L\) und summiert seinen Zyklusbeitrag exakt auf, ohne jemals die \(Q\) Matrixeinträge selbst zu durchlaufen.
Die C++-, Python- und Java-Implementierungen folgen demselben zahlentheoretischen Ablauf.
Zunächst wird einmal ein Primzahlsieb erzeugt. Für ein festes Paar \((n,m)\) bildet die Implementierung \(s=nm\), faktorisiert \(s-1\), \(s+1\) und \(s^2+1\) und fasst die Exponenten zur Zerlegung von \(L=s^4-1\) zusammen. Weil verschiedene Paare denselben Wert \(s\) haben können, wird diese Faktorisierung zwischengespeichert und wiederverwendet. Auch Faktorisierungen von Zahlen der Form \(p-1\) werden gecacht, da sie beim Reduzieren von \(\varphi(p^k)\) auf die exakte Ordnung \(\operatorname{ord}_{p^k}(\alpha)\) mehrfach gebraucht werden.
Für jede Primzahlpotenz \(p^k\mid L\) werden \(\varphi(p^k)\) und \(\operatorname{ord}_{p^k}(\alpha)\) vorab berechnet. Danach läuft eine DFS über die Teiler: Auf jeder Rekursionsebene wird ein Exponent für eine Primzahl gewählt, der laufende Phi-Beitrag multipliziert, die laufende Ordnung per \(\operatorname{lcm}\) aktualisiert und zur nächsten Primzahl gegangen. An jedem Blatt wird der Teilerbeitrag
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}$$
zur Zykluszahl \(C_L\) addiert. Der zurückgegebene Vertauschungswert ist also \(Q-1-C_L\).
Die äußeren Schleifen summieren diese Größe über alle \(2\le n\le m\le 100\). Zusätzlich vergleichen die Implementierungen die Teilersumme mit expliziten Zykluszerlegungen in kleinen Fällen; das gewöhnliche \(3\times 4\)-Rechteck liefert dabei exakt \(8\) Vertauschungen und bestätigt die Herleitung.
Für ein einzelnes Paar \((n,m)\) wird niemals über alle \(Q=(nm)^4\) Positionen iteriert. Der Aufwand steckt stattdessen in drei Aufgaben: der Faktorisierung von \(s-1\), \(s+1\) und \(s^2+1\), der Berechnung der multiplikativen Ordnungen auf den relevanten Primzahlpotenzen und der Enumeration der \(\tau(L)\) Teiler von \(L\) per DFS über Primfaktorexponenten. In der Praxis ist das viel kleiner als ein brute-force-Zykluslauf auf der vollständigen Permutation.
Der Speicherbedarf bleibt moderat. Gespeichert werden vor allem die Primzahlliste, die Caches für wiederkehrende Faktorisierungen und die Tabellen der Primzahlpotenzen für das aktuelle Paar. Effizient ist das Verfahren deshalb, weil es mit der Faktorisierung von \(L=(nm)^4-1\) arbeitet und nicht mit den \((nm)^4\) Matrixeinträgen selbst.
Her \(2\le n\le m\le 100\) çifti için problem, kenar uzunlukları \(n^4\) ve \(m^4\) olan bir dikdörtgen alır. Hücreler bir kez row-major düzende, bir kez de column-major düzende numaralandırılır; bu iki numaralandırma arasındaki geçiş, toplam \((nm)^4\) konum üzerinde bir permütasyon oluşturur. Her çift için bu permütasyonu gerçekleştirmek adına gereken en az swap sayısı bulunur ve bu değerler toplanır.
Tüm permütasyon çevrimlerini doğrudan gezmek mümkün değildir; çünkü tek bir çift için bile \(Q=(nm)^4\) kadar konum vardır. Uygulamalar, transpozisyon permütasyonunu modüler çarpma biçimine dönüştürüp çevrim sayısını \(Q-1\) sayısının bölenleri üzerinden hesaplayarak işi çözer.
Satır sayısını \(r=m^4\), sütun sayısını \(c=n^4\) olarak yazalım. Ayrıca
$$Q=rc=(nm)^4,\qquad L=Q-1,\qquad \alpha=r=m^4$$
tanımlarını yapalım. Böylece tüm problem tek bir modüler permütasyonun çevrim yapısını saymaya dönüşür.
\(0\le i\lt r\) ve \(0\le j\lt c\) olacak şekilde satırı \(i\), sütunu \(j\) olan bir hücre seçelim. Bunun row-major indisi
$$x=ic+j,$$
column-major indisi ise
$$y=jr+i$$
olur. Şimdi \(rx\) hesabını yapalım:
$$rx=r(ic+j)=irc+rj=iQ+rj\equiv i+rj=y \pmod{Q-1}.$$
Dolayısıyla son konum hariç bütün indisler için
$$\pi(x)\equiv \alpha x \pmod L,\qquad 0\le x\lt L$$
eşitliği geçerlidir. Geriye kalan \(x=L=Q-1\) indisi ise ek bir sabit noktadır. Ayrıca
$$L=(nm)^4-1\equiv -1 \pmod m$$
olduğu için \(\gcd(\alpha,L)=1\) ve \(\alpha\) ile çarpma modulo \(L\) üzerinde gerçekten bir permütasyondur.
\(Q\) elemanlı bir permütasyonun toplam çevrim sayısı \(C\) ise, gerekli en az swap sayısı \(Q-C\) olur; çünkü uzunluğu \(t\) olan bir çevrimi çözmek için tam \(t-1\) swap gerekir. Yani asıl iş çevrim sayısını bulmaktır.
\(x\in \mathbb{Z}/L\mathbb{Z}\) için
$$d=\frac{L}{\gcd(x,L)}$$
tanımını yapalım. Bu \(d\), \(x\)'in çevrimsel grup \(\mathbb{Z}/L\mathbb{Z}\) içindeki toplamsal mertebesidir. \(\alpha\) modulo \(L\) tersinir olduğu için \(\gcd(x,L)\) değeri, dolayısıyla \(d\) de değişmez. Böylece permütasyon, \(L\)'nin her \(d\mid L\) böleni için birer tane olmak üzere korunmuş katmanlara ayrılır.
Toplamsal mertebesi tam olarak \(d\) olan kalıntı sayısı \(\varphi(d)\)'dir; bunlar, \(\mathbb{Z}/L\mathbb{Z}\) içindeki \(d\) elemanlı tek alt grubun üreteçleridir.
Şöyle yazalım:
$$g=\gcd(x,L),\qquad x=gu,\qquad L=gd,$$
ve burada \(\gcd(u,d)=1\) olsun. \(x\)'in \(t\) adım sonra kendisine dönmesi için
$$\alpha^t x\equiv x \pmod L$$
olmalıdır. \(x=gu\) ve \(L=gd\) yerine yazılırsa
$$gd\mid g(\alpha^t-1)u\iff d\mid(\alpha^t-1)u$$
elde edilir. \(u\), modulo \(d\) tersinir olduğundan bu koşul
$$\alpha^t\equiv 1 \pmod d$$
ile denktir. Demek ki \(d\) katmanındaki her yörüngenin uzunluğu
$$\operatorname{ord}_d(\alpha)$$
olur. Katmanda \(\varphi(d)\) eleman bulunduğu için bu katmanın çevrim katkısı
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}$$
şeklindedir.
Bütün bölenler üzerindeki toplam, modüler bölümdeki çevrim sayısını verir:
$$C_L=\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.$$
Burada \(\operatorname{ord}_1(\alpha)=1\) kabul edilir. Bu toplam \(x=0\) sabit noktasını zaten içerir. \(x=L=Q-1\) ise modüler kümenin dışındaki ek sabit noktadır; dolayısıyla toplam çevrim sayısı
$$C=C_L+1$$
olur. Sonuç olarak \((n,m)\) çifti için swap sayısı
$$\boxed{\text{swap}=Q-1-\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.}$$
Gerçek problem dördüncü kuvvetleri kullanır, ama aynı mekanizma \(r=4\), \(c=3\) olan küçük bir sıradan dikdörtgende açıkça görülür. Bu durumda
$$Q=12,\qquad L=11,\qquad \alpha=4$$
ve \(0\le x\lt 11\) için
$$\pi(x)\equiv 4x \pmod{11}$$
olur. \(11\)'in tek bölenleri \(1\) ve \(11\) olduğundan
$$C_{11}=1+\frac{\varphi(11)}{\operatorname{ord}_{11}(4)}=1+\frac{10}{5}=3$$
bulunur. Gerçekten de kalıntılar
$$0,$$
$$1\to 4\to 5\to 9\to 3\to 1,$$
$$2\to 8\to 10\to 7\to 6\to 2$$
çevrimlerine ayrılır ve on ikinci konum \(x=11\) ek sabit noktadır. Böylece toplam çevrim sayısı \(4\), minimum swap sayısı da
$$12-4=8$$
olur. Uygulamaların küçük doğrulama kontrolü de tam olarak bu örneği kullanır.
\(s=nm\) olsun. O zaman
$$L=s^4-1=(s-1)(s+1)(s^2+1)$$
elde edilir. \(s\le 10^4\) olduğundan \(s-1\), \(s+1\) ve \(s^2+1\) yönetilebilir büyüklüktedir. Bu üç sayıyı çarpanlarına ayırmak, \(L\)'nin tam asal çarpan ayrışımını verir.
Her \(p^k\mid L\) asal kuvveti için
$$\operatorname{ord}_{p^k}(\alpha)\mid \varphi(p^k)=p^{k-1}(p-1)$$
olur. Tam mertebe, \(\varphi(p^k)\) ile başlanıp modüler üs testi
$$\alpha^{\,\varphi(p^k)/q}\equiv 1 \pmod{p^k}$$
doğru kaldığı sürece asal çarpanları ayıklayarak bulunur.
Eğer
$$d=\prod_i p_i^{e_i}$$
ise, çarpımsallık ve Çin kalan teoremi sayesinde
$$\varphi(d)=\prod_i \varphi(p_i^{e_i}),\qquad \operatorname{ord}_d(\alpha)=\operatorname{lcm}_i\operatorname{ord}_{p_i^{e_i}}(\alpha)$$
olur. Böylece \(0\le e_i\le v_{p_i}(L)\) seçimleri üzerinde çalışan bir DFS, her \(d\mid L\) bölenini tek tek ziyaret edip çevrim katkısını matristeki \(Q\) hücreyi dolaşmadan toplar.
C++, Python ve Java uygulamaları aynı sayı teorisi hattını izler.
Önce tek seferlik bir asal sayı eleği kurulur. Sabit bir \((n,m)\) çifti için uygulama \(s=nm\) değerini oluşturur, \(s-1\), \(s+1\) ve \(s^2+1\) sayılarının çarpanlarını bulur ve üsleri birleştirerek \(L=s^4-1\)'in ayrışımını elde eder. Aynı \(s\) değeri farklı çiftlerden gelebileceği için bu ayrışım önbelleğe alınır. Ayrıca \(p-1\) biçimindeki sayıların çarpanları da saklanır; çünkü \(\varphi(p^k)\)'yi tam mertebe \(\operatorname{ord}_{p^k}(\alpha)\)'ya indirgerken bunlar tekrar tekrar kullanılır.
Her \(p^k\mid L\) asal kuvveti için \(\varphi(p^k)\) ve \(\operatorname{ord}_{p^k}(\alpha)\) önceden hesaplanır. Sonra bölenler üzerinde bir DFS çalışır: her özyineleme seviyesinde bir asalın üssü seçilir, birikmiş phi katkısı çarpılır, birikmiş mertebe \(\operatorname{lcm}\) ile güncellenir ve sonraki asala geçilir. Her yaprakta
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}$$
miktarı çevrim toplamı \(C_L\)'ye eklenir. Döndürülen swap değeri de doğal olarak \(Q-1-C_L\) olur.
Dış döngüler bu değeri bütün \(2\le n\le m\le 100\) çiftleri için toplar. Uygulamalar ayrıca formülü küçük örneklerde açık çevrim ayrışımıyla karşılaştırır; sıradan \(3\times 4\) dikdörtgen için çıkan \(8\) swap değeri, yukarıdaki türetimi doğrular.
Tek bir \((n,m)\) çifti için algoritma hiçbir zaman \(Q=(nm)^4\) adet konumun tamamını dolaşmaz. Maliyet üç ana yerde toplanır: \(s-1\), \(s+1\) ve \(s^2+1\)'in çarpanlara ayrılması, ilgili asal kuvvetlerde çarpımsal mertebelerin hesaplanması ve \(L\)'nin \(\tau(L)\) adet böleninin DFS ile gezilmesi. Pratikte bu, tüm transpozisyon permütasyonunu brute-force çevrim ayrışımına sokmaktan çok daha küçüktür.
Bellek kullanımı düşüktür. Başlıca veri yapıları asal listesi, tekrar kullanılan çarpan önbellekleri ve o anki çift için tutulan asal kuvvet tablolarıdır. Yöntem, \((nm)^4\) hücrelerle değil, \(L=(nm)^4-1\)'in asal çarpan yapısıyla çalıştığı için verimlidir.
Para cada par \(2\le n\le m\le 100\), el problema considera un rectángulo cuyas longitudes laterales son \(n^4\) y \(m^4\). Sus celdas se listan una vez en orden row-major y otra vez en orden column-major, de modo que el cambio entre ambas numeraciones es una permutación de las \((nm)^4\) posiciones. Para cada par hay que hallar el número mínimo de intercambios necesario para realizar esa permutación y luego sumar esos valores.
Un recorrido directo por todos los ciclos sería inviable, porque incluso un solo par ya produce \(Q=(nm)^4\) posiciones. La solución funciona al convertir la permutación de transposición en una multiplicación modular y contar sus ciclos a través de los divisores de \(Q-1\).
Escribamos \(r=m^4\) para el número de filas y \(c=n^4\) para el número de columnas. Definimos
$$Q=rc=(nm)^4,\qquad L=Q-1,\qquad \alpha=r=m^4.$$
Con esta notación, toda la tarea se reduce a estudiar la estructura cíclica de una sola permutación modular.
Tomemos una celda en la fila \(i\) y la columna \(j\), con \(0\le i\lt r\) y \(0\le j\lt c\). Su índice row-major es
$$x=ic+j,$$
mientras que su índice column-major es
$$y=jr+i.$$
Ahora calculemos \(rx\):
$$rx=r(ic+j)=irc+rj=iQ+rj\equiv i+rj=y \pmod{Q-1}.$$
Por tanto, para todos los índices salvo el último, se cumple
$$\pi(x)\equiv \alpha x \pmod L,\qquad 0\le x\lt L.$$
El índice que falta, \(x=L=Q-1\), es un punto fijo adicional. Además, como
$$L=(nm)^4-1\equiv -1 \pmod m,$$
tenemos \(\gcd(\alpha,L)=1\), así que multiplicar por \(\alpha\) realmente define una permutación módulo \(L\).
Si una permutación sobre \(Q\) elementos tiene \(C\) ciclos en total, el número mínimo de intercambios necesario es \(Q-C\), porque un ciclo de longitud \(t\) requiere exactamente \(t-1\) intercambios. Todo el problema queda reducido, entonces, a contar ciclos.
Para un residuo \(x\in \mathbb{Z}/L\mathbb{Z}\), definimos
$$d=\frac{L}{\gcd(x,L)}.$$
Ese \(d\) es el orden aditivo de \(x\) dentro del grupo cíclico \(\mathbb{Z}/L\mathbb{Z}\). Como \(\alpha\) es invertible módulo \(L\), la multiplicación por \(\alpha\) conserva \(\gcd(x,L)\) y, por tanto, también conserva \(d\). La permutación se descompone así en capas invariantes, una por cada divisor \(d\mid L\).
Hay exactamente \(\varphi(d)\) residuos de orden aditivo \(d\): son los generadores del único subgrupo de tamaño \(d\) dentro de \(\mathbb{Z}/L\mathbb{Z}\).
Escribamos
$$g=\gcd(x,L),\qquad x=gu,\qquad L=gd,$$
con \(\gcd(u,d)=1\). La condición de que \(x\) vuelva a sí mismo tras \(t\) pasos es
$$\alpha^t x\equiv x \pmod L.$$
Sustituyendo \(x=gu\) y \(L=gd\), obtenemos
$$gd\mid g(\alpha^t-1)u\iff d\mid(\alpha^t-1)u.$$
Como \(u\) es invertible módulo \(d\), esto equivale a
$$\alpha^t\equiv 1 \pmod d.$$
Por lo tanto, toda órbita en la capa correspondiente a \(d\) tiene longitud
$$\operatorname{ord}_d(\alpha),$$
es decir, el orden multiplicativo de \(\alpha\) módulo \(d\). Como la capa contiene \(\varphi(d)\) elementos, aporta
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}$$
ciclos.
Al sumar todas esas contribuciones sobre los divisores de \(L\), obtenemos el número de ciclos en la parte modular:
$$C_L=\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)},$$
con la convención natural \(\operatorname{ord}_1(\alpha)=1\). Esta suma ya incluye el punto fijo \(x=0\). El índice \(x=L=Q-1\) aporta otro punto fijo fuera del conjunto modular, así que el número total de ciclos es
$$C=C_L+1.$$
En consecuencia, para el par \((n,m)\) se obtiene
$$\boxed{\text{intercambios}=Q-1-\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.}$$
El problema real usa cuartas potencias, pero el mismo mecanismo ya se ve en un rectángulo pequeño ordinario con \(r=4\) y \(c=3\). Entonces
$$Q=12,\qquad L=11,\qquad \alpha=4,$$
de modo que para \(0\le x\lt 11\)
$$\pi(x)\equiv 4x \pmod{11}.$$
Como los únicos divisores de \(11\) son \(1\) y \(11\), resulta
$$C_{11}=1+\frac{\varphi(11)}{\operatorname{ord}_{11}(4)}=1+\frac{10}{5}=3.$$
En efecto, los residuos se dividen en
$$0,$$
$$1\to 4\to 5\to 9\to 3\to 1,$$
$$2\to 8\to 10\to 7\to 6\to 2,$$
y la duodécima posición \(x=11\) es el punto fijo adicional. Así, el número total de ciclos es \(4\) y el número mínimo de intercambios vale
$$12-4=8.$$
Ese es exactamente el pequeño caso de control que usan las implementaciones.
Sea \(s=nm\). Entonces
$$L=s^4-1=(s-1)(s+1)(s^2+1).$$
Como \(s\le 10^4\), los enteros \(s-1\), \(s+1\) y \(s^2+1\) siguen siendo moderados. Factorizar esos tres números basta para recuperar la descomposición prima completa de \(L\).
Para cada potencia prima \(p^k\mid L\), se cumple
$$\operatorname{ord}_{p^k}(\alpha)\mid \varphi(p^k)=p^{k-1}(p-1).$$
El orden exacto se obtiene partiendo de \(\varphi(p^k)\) y eliminando factores primos mientras el test modular
$$\alpha^{\,\varphi(p^k)/q}\equiv 1 \pmod{p^k}$$
siga siendo cierto.
Si
$$d=\prod_i p_i^{e_i},$$
entonces la multiplicatividad y el teorema chino del resto dan
$$\varphi(d)=\prod_i \varphi(p_i^{e_i}),\qquad \operatorname{ord}_d(\alpha)=\operatorname{lcm}_i\operatorname{ord}_{p_i^{e_i}}(\alpha).$$
Una búsqueda en profundidad sobre todas las elecciones \(0\le e_i\le v_{p_i}(L)\) visita así cada divisor \(d\mid L\) y suma su contribución exacta, sin tocar nunca las \(Q\) celdas del rectángulo.
Las implementaciones en C++, Python y Java siguen el mismo esquema aritmético.
Primero se construye una criba de primos una sola vez. Para un par fijo \((n,m)\), la implementación forma \(s=nm\), factoriza \(s-1\), \(s+1\) y \(s^2+1\), y fusiona esos exponentes en la factorización de \(L=s^4-1\). Como distintos pares pueden compartir el mismo producto \(s\), esa factorización se guarda y se reutiliza. También se almacenan las factorizaciones de números de la forma \(p-1\), porque aparecen repetidamente al reducir \(\varphi(p^k)\) hasta el orden exacto \(\operatorname{ord}_{p^k}(\alpha)\).
Para cada potencia prima \(p^k\mid L\), la implementación precomputa \(\varphi(p^k)\) y \(\operatorname{ord}_{p^k}(\alpha)\). Después ejecuta una DFS sobre los divisores: en cada nivel elige el exponente de un primo, multiplica la contribución acumulada de phi, actualiza el orden acumulado mediante un \(\operatorname{lcm}\) y continúa. En cada hoja añade
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}$$
al total de ciclos \(C_L\). Por eso el valor devuelto para el número de intercambios es \(Q-1-C_L\).
Los bucles externos suman ese resultado para todos los \(2\le n\le m\le 100\). Además, las implementaciones comparan la fórmula con descomposiciones explícitas en ciclos para casos pequeños; el rectángulo ordinario \(3\times 4\) produce exactamente \(8\) intercambios y confirma toda la derivación.
Para un par \((n,m)\), el algoritmo nunca recorre las \(Q=(nm)^4\) posiciones. El trabajo se concentra en factorizar \(s-1\), \(s+1\) y \(s^2+1\), calcular órdenes multiplicativos sobre las potencias primas relevantes y enumerar los \(\tau(L)\) divisores de \(L\) mediante una DFS sobre exponentes primos. En la práctica esto es muchísimo menor que un recorrido bruto por todos los ciclos de la permutación completa.
El uso de memoria es moderado. Los datos principales son la lista de primos, las cachés de factorizaciones repetidas y las tablas de potencias primas del par actual. El método es eficiente porque trabaja con la factorización de \(L=(nm)^4-1\), no con las \((nm)^4\) entradas de la matriz.
对于每个满足 \(2\le n\le m\le 100\) 的整数对，题目考虑一个边长分别为 \(n^4\) 与 \(m^4\) 的矩形。把所有单元先按 row-major 顺序线性编号，再按 column-major 顺序线性编号，这两种编号之间的对应关系就构成了作用在 \((nm)^4\) 个位置上的一个置换。对每一对 \((n,m)\)，要求的是实现这个置换所需的最少交换次数，然后把这些值全部加总。
如果真的对整个置换直接做循环分解，规模会完全失控，因为单个整数对就已经对应 \(Q=(nm)^4\) 个位置。可行做法的关键在于：这个“按行存储到按列存储”的置换可以改写成一个模乘映射，而循环数又可以通过 \(Q-1\) 的所有除数精确统计出来。
记矩形的行数为 \(r=m^4\)，列数为 \(c=n^4\)，并定义
$$Q=rc=(nm)^4,\qquad L=Q-1,\qquad \alpha=r=m^4.$$
这样一来，问题就变成了分析一个模意义下置换的循环结构。
设某个单元位于第 \(i\) 行、第 \(j\) 列，其中 \(0\le i\lt r\)、\(0\le j\lt c\)。它的 row-major 线性下标是
$$x=ic+j,$$
对应的 column-major 线性下标是
$$y=jr+i.$$
现在直接计算 \(rx\)：
$$rx=r(ic+j)=irc+rj=iQ+rj\equiv i+rj=y \pmod{Q-1}.$$
因此，除了最后一个位置以外，这个重编号置换都满足
$$\pi(x)\equiv \alpha x \pmod L,\qquad 0\le x\lt L.$$
剩下的那个下标 \(x=L=Q-1\) 是一个额外不动点。又因为
$$L=(nm)^4-1\equiv -1 \pmod m,$$
所以 \(\gcd(\alpha,L)=1\)，这说明“乘以 \(\alpha\)”在模 \(L\) 的剩余类上确实给出了一个置换。
如果一个作用在 \(Q\) 个元素上的置换总共有 \(C\) 个循环，那么实现它所需的最少交换次数就是 \(Q-C\)，因为长度为 \(t\) 的一个循环恰好需要 \(t-1\) 次交换。于是问题被压缩成了一个纯粹的循环计数问题。
对任意 \(x\in \mathbb{Z}/L\mathbb{Z}\)，定义
$$d=\frac{L}{\gcd(x,L)}.$$
这个 \(d\) 正是 \(x\) 在循环群 \(\mathbb{Z}/L\mathbb{Z}\) 中的加法阶。由于 \(\alpha\) 在模 \(L\) 下可逆，乘以 \(\alpha\) 不会改变 \(\gcd(x,L)\)，因此也不会改变 \(d\)。这意味着整个置换会自动分裂成若干个不相交且彼此独立的层，每个除数 \(d\mid L\) 对应一层。
加法阶恰好等于 \(d\) 的剩余类一共有 \(\varphi(d)\) 个；它们正是 \(\mathbb{Z}/L\mathbb{Z}\) 中那个大小为 \(d\) 的唯一子群的全部生成元。
把
$$g=\gcd(x,L),\qquad x=gu,\qquad L=gd$$
写出来，并满足 \(\gcd(u,d)=1\)。如果 \(x\) 经过 \(t\) 次作用后回到自己，就必须有
$$\alpha^t x\equiv x \pmod L.$$
代入 \(x=gu\)、\(L=gd\) 以后，这等价于
$$gd\mid g(\alpha^t-1)u\iff d\mid(\alpha^t-1)u.$$
由于 \(u\) 在模 \(d\) 下可逆，上式进一步等价于
$$\alpha^t\equiv 1 \pmod d.$$
所以处在加法阶层 \(d\) 内的每一条轨道，其长度都恰好等于
$$\operatorname{ord}_d(\alpha),$$
也就是 \(\alpha\) 模 \(d\) 的乘法阶。既然这一层有 \(\varphi(d)\) 个元素，它贡献的循环数就是
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.$$
把所有除数层的贡献都加起来，就得到模部分的循环总数：
$$C_L=\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.$$
这里约定 \(\operatorname{ord}_1(\alpha)=1\)。这个和已经把 \(x=0\) 这个不动点算进去了，而 \(x=L=Q-1\) 还会额外贡献一个不动点，因此总循环数为
$$C=C_L+1.$$
于是，对整数对 \((n,m)\) 而言，最少交换次数满足
$$\boxed{\text{交换次数}=Q-1-\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.}$$
虽然题目真正处理的是四次方尺寸，但同样的机制在一个普通的小矩形里就已经完全显现。取 \(r=4\)、\(c=3\)，则
$$Q=12,\qquad L=11,\qquad \alpha=4,$$
于是对 \(0\le x\lt 11\) 有
$$\pi(x)\equiv 4x \pmod{11}.$$
因为 \(11\) 的除数只有 \(1\) 与 \(11\)，所以
$$C_{11}=1+\frac{\varphi(11)}{\operatorname{ord}_{11}(4)}=1+\frac{10}{5}=3.$$
这与直接写出的循环分解完全一致：
$$0,$$
$$1\to 4\to 5\to 9\to 3\to 1,$$
$$2\to 8\to 10\to 7\to 6\to 2.$$
再加上第十二个位置 \(x=11\) 这个额外不动点，总循环数就是 \(4\)，因此最少交换次数为
$$12-4=8.$$
这正是实现里用来做小规模校验的例子。
设 \(s=nm\)，那么
$$L=s^4-1=(s-1)(s+1)(s^2+1).$$
由于 \(s\le 10^4\)，所以 \(s-1\)、\(s+1\) 和 \(s^2+1\) 都还只是中等规模的整数。只要把这三个因子做质因数分解，就能恢复 \(L\) 的完整分解。
对每个满足 \(p^k\mid L\) 的质数幂，都有
$$\operatorname{ord}_{p^k}(\alpha)\mid \varphi(p^k)=p^{k-1}(p-1).$$
实现中先把 \(\varphi(p^k)\) 当作候选值，然后不断尝试除去它的质因子；只要模幂检验
$$\alpha^{\,\varphi(p^k)/q}\equiv 1 \pmod{p^k}$$
仍然成立，就说明这个因子还可以继续消去。
如果
$$d=\prod_i p_i^{e_i},$$
那么由乘法性与中国剩余定理可知
$$\varphi(d)=\prod_i \varphi(p_i^{e_i}),\qquad \operatorname{ord}_d(\alpha)=\operatorname{lcm}_i\operatorname{ord}_{p_i^{e_i}}(\alpha).$$
因此，只需对全部指数选择 \(0\le e_i\le v_{p_i}(L)\) 做一次深度优先遍历，就能枚举每个除数 \(d\mid L\) 并累加其精确贡献，而完全不必直接遍历矩形的 \(Q\) 个单元。
C++、Python 和 Java 三份实现遵循的是同一条数论计算路线。
实现先一次性建立质数表。对固定的 \((n,m)\)，程序构造 \(s=nm\)，分解 \(s-1\)、\(s+1\) 与 \(s^2+1\)，再把相同质数的指数合并，从而得到 \(L=s^4-1\) 的完整质因数分解。由于不同的整数对可能拥有相同的乘积 \(s\)，这部分分解会被缓存复用。形如 \(p-1\) 的分解也会被缓存，因为在把 \(\varphi(p^k)\) 缩减到精确的 \(\operatorname{ord}_{p^k}(\alpha)\) 时会多次用到它们。
对于每个质数幂 \(p^k\mid L\)，实现都会先算好 \(\varphi(p^k)\) 与 \(\operatorname{ord}_{p^k}(\alpha)\)。随后进行一次针对除数的 DFS：每层递归为某个质数选择指数，把当前的 phi 贡献乘上对应因子，再用 \(\operatorname{lcm}\) 更新当前乘法阶。到达叶子时，就向循环总数 \(C_L\) 加上
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.$$
因此每一对 \((n,m)\) 返回的交换次数自然就是 \(Q-1-C_L\)。
外层双循环再把所有 \(2\le n\le m\le 100\) 的结果相加。实现还会把这个公式与小规模情形的显式循环分解逐项比较；例如普通的 \(3\times 4\) 矩形恰好需要 \(8\) 次交换，这与上面的理论完全一致。
对于单个 \((n,m)\)，算法从不在 \(Q=(nm)^4\) 个位置上做显式遍历。主要开销集中在三件事上：分解 \(s-1\)、\(s+1\) 和 \(s^2+1\)；计算相关质数幂上的乘法阶；以及通过质因子指数 DFS 枚举 \(L\) 的 \(\tau(L)\) 个除数。和直接对完整置换做循环分解相比，这在实践中小得多。
内存消耗也比较温和。主要数据结构就是质数表、重复利用的分解缓存，以及当前整数对所需的质数幂表。方法之所以高效，正是因为它处理的是 \(L=(nm)^4-1\) 的质因数结构，而不是 \((nm)^4\) 个矩阵位置本身。
Для каждой пары \(2\le n\le m\le 100\) рассматривается прямоугольник со сторонами \(n^4\) и \(m^4\). Его клетки один раз нумеруются в порядке row-major, а затем в порядке column-major, и переход между этими двумя линейными нумерациями задает перестановку всех \((nm)^4\) позиций. Для каждой пары нужно найти минимальное число обменов, необходимое для реализации этой перестановки, а затем просуммировать такие значения.
Прямой обход всех циклов здесь бесполезен, потому что уже для одной пары появляется \(Q=(nm)^4\) позиций. Рабочий подход основан на том, что перестановка транспонирования сводится к умножению по модулю, а число ее циклов выражается через делители числа \(Q-1\).
Обозначим число строк через \(r=m^4\), а число столбцов через \(c=n^4\). Введем
$$Q=rc=(nm)^4,\qquad L=Q-1,\qquad \alpha=r=m^4.$$
После этого вся задача становится задачей о циклической структуре одной модульной перестановки.
Пусть клетка находится в строке \(i\) и столбце \(j\), где \(0\le i\lt r\) и \(0\le j\lt c\). Ее row-major индекс равен
$$x=ic+j,$$
а column-major индекс равен
$$y=jr+i.$$
Теперь вычислим \(rx\):
$$rx=r(ic+j)=irc+rj=iQ+rj\equiv i+rj=y \pmod{Q-1}.$$
Значит, для всех индексов, кроме последнего, выполняется
$$\pi(x)\equiv \alpha x \pmod L,\qquad 0\le x\lt L.$$
Оставшийся индекс \(x=L=Q-1\) является дополнительной неподвижной точкой. Кроме того, из
$$L=(nm)^4-1\equiv -1 \pmod m$$
следует \(\gcd(\alpha,L)=1\), то есть умножение на \(\alpha\) действительно задает перестановку по модулю \(L\).
Если перестановка на \(Q\) элементах имеет \(C\) циклов, то минимальное число обменов равно \(Q-C\), потому что цикл длины \(t\) требует ровно \(t-1\) обменов. Поэтому дальше нужно только уметь считать число циклов.
Для любого остатка \(x\in \mathbb{Z}/L\mathbb{Z}\) определим
$$d=\frac{L}{\gcd(x,L)}.$$
Это число \(d\) и есть аддитивный порядок элемента \(x\) в циклической группе \(\mathbb{Z}/L\mathbb{Z}\). Поскольку \(\alpha\) обратимо по модулю \(L\), умножение на \(\alpha\) не меняет \(\gcd(x,L)\), а значит не меняет и \(d\). Поэтому перестановка автоматически распадается на инвариантные слои, по одному для каждого делителя \(d\mid L\).
Ровно \(\varphi(d)\) остатков имеют аддитивный порядок \(d\): это все образующие единственной подгруппы размера \(d\) внутри \(\mathbb{Z}/L\mathbb{Z}\).
Запишем
$$g=\gcd(x,L),\qquad x=gu,\qquad L=gd,$$
где \(\gcd(u,d)=1\). Возврат элемента \(x\) к самому себе через \(t\) шагов означает
$$\alpha^t x\equiv x \pmod L.$$
Подставляя \(x=gu\) и \(L=gd\), получаем
$$gd\mid g(\alpha^t-1)u\iff d\mid(\alpha^t-1)u.$$
Так как \(u\) обратим по модулю \(d\), это равносильно условию
$$\alpha^t\equiv 1 \pmod d.$$
Следовательно, каждая орбита в слое с параметром \(d\) имеет длину
$$\operatorname{ord}_d(\alpha),$$
то есть мультипликативный порядок \(\alpha\) по модулю \(d\). Поскольку в таком слое \(\varphi(d)\) элементов, он дает
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}$$
циклов.
Суммирование по всем делителям \(L\) дает число циклов в модульной части:
$$C_L=\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)},$$
где по соглашению \(\operatorname{ord}_1(\alpha)=1\). Здесь уже учтена неподвижная точка \(x=0\). Индекс \(x=L=Q-1\) дает еще одну неподвижную точку вне модульного множества, так что всего
$$C=C_L+1.$$
Значит, для пары \((n,m)\) получаем
$$\boxed{\text{обмены}=Q-1-\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.}$$
Хотя в задаче используются четвертые степени, тот же механизм уже полностью виден на маленьком обычном прямоугольнике с \(r=4\) и \(c=3\). Тогда
$$Q=12,\qquad L=11,\qquad \alpha=4,$$
и для \(0\le x\lt 11\) имеем
$$\pi(x)\equiv 4x \pmod{11}.$$
Поскольку у \(11\) только два делителя, \(1\) и \(11\), получается
$$C_{11}=1+\frac{\varphi(11)}{\operatorname{ord}_{11}(4)}=1+\frac{10}{5}=3.$$
И действительно, остатки распадаются на
$$0,$$
$$1\to 4\to 5\to 9\to 3\to 1,$$
$$2\to 8\to 10\to 7\to 6\to 2,$$
а двенадцатая позиция \(x=11\) является дополнительной неподвижной точкой. Значит, общее число циклов равно \(4\), а минимальное число обменов равно
$$12-4=8.$$
Именно этот малый пример используется в реализациях как быстрая проверка корректности.
Положим \(s=nm\). Тогда
$$L=s^4-1=(s-1)(s+1)(s^2+1).$$
Так как \(s\le 10^4\), числа \(s-1\), \(s+1\) и \(s^2+1\) остаются умеренного размера. Достаточно факторизовать эти три множителя, чтобы восстановить полное разложение \(L\) на простые множители.
Для каждой простой степени \(p^k\mid L\) верно
$$\operatorname{ord}_{p^k}(\alpha)\mid \varphi(p^k)=p^{k-1}(p-1).$$
Точный порядок находится так: сначала берется \(\varphi(p^k)\), затем из него последовательно выбрасываются простые множители, пока модульный тест
$$\alpha^{\,\varphi(p^k)/q}\equiv 1 \pmod{p^k}$$
остается истинным.
Если
$$d=\prod_i p_i^{e_i},$$
то из мультипликативности и китайской теоремы об остатках следует
$$\varphi(d)=\prod_i \varphi(p_i^{e_i}),\qquad \operatorname{ord}_d(\alpha)=\operatorname{lcm}_i\operatorname{ord}_{p_i^{e_i}}(\alpha).$$
Поэтому DFS по всем вариантам \(0\le e_i\le v_{p_i}(L)\) перечисляет каждый делитель \(d\mid L\) и суммирует его точный вклад, ни разу не перебирая сами \(Q\) позиции прямоугольника.
Реализации на C++, Python и Java выполняют один и тот же арифметический план.
Сначала один раз строится решето простых чисел. Для фиксированной пары \((n,m)\) реализация образует \(s=nm\), факторизует \(s-1\), \(s+1\) и \(s^2+1\), а затем объединяет показатели простых, получая разложение \(L=s^4-1\). Поскольку разные пары могут иметь одинаковое произведение \(s\), эта факторизация кэшируется и используется повторно. Отдельно сохраняются факторизации чисел вида \(p-1\), потому что они многократно нужны при уменьшении \(\varphi(p^k)\) до точного порядка \(\operatorname{ord}_{p^k}(\alpha)\).
Для каждой простой степени \(p^k\mid L\) заранее вычисляются \(\varphi(p^k)\) и \(\operatorname{ord}_{p^k}(\alpha)\). Затем запускается DFS по делителям: на каждом уровне выбирается показатель одной простой, умножается текущий вклад phi, обновляется текущий порядок через \(\operatorname{lcm}\), и рекурсия идет дальше. В каждом листе к числу циклов \(C_L\) прибавляется
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.$$
Поэтому итоговое значение для числа обменов равно \(Q-1-C_L\).
Внешние циклы суммируют этот результат по всем \(2\le n\le m\le 100\). Кроме того, реализации сравнивают формулу с явными разложениями на циклы в малых случаях; например, обычный прямоугольник \(3\times 4\) дает ровно \(8\) обменов, что полностью совпадает с теорией.
Для одной пары \((n,m)\) алгоритм никогда не проходит по всем \(Q=(nm)^4\) позициям. Основные затраты приходятся на факторизацию чисел \(s-1\), \(s+1\) и \(s^2+1\), вычисление мультипликативных порядков на нужных простых степенях и перечисление \(\tau(L)\) делителей числа \(L\) через DFS по показателям простых. На практике это намного дешевле, чем прямой обход циклов всей перестановки.
Память расходуется умеренно. Хранятся список простых, кэши повторяющихся факторизаций и таблицы простых степеней для текущей пары. Эффективность достигается за счет работы с факторизацией \(L=(nm)^4-1\), а не с \((nm)^4\) отдельными позициями матрицы.
لكل زوج \(2\le n\le m\le 100\)، تنظر المسألة إلى مستطيل طولا ضلعيه \(n^4\) و\(m^4\). تُرقَّم خلاياه مرة بترتيب row-major ومرة بترتيب column-major، فينشأ عن التحويل بين الترقيمين تبديل على جميع المواضع وعددها \((nm)^4\). المطلوب لكل زوج هو أقل عدد من عمليات التبديل اللازمة لتنفيذ هذا التبديل، ثم جمع هذه القيم كلها.
السير المباشر على جميع الدورات غير عملي إطلاقًا، لأن زوجًا واحدًا فقط ينتج \(Q=(nm)^4\) موضعًا. الفكرة الفعالة هي تحويل تبديل النقل إلى ضرب معياري، ثم عدّ الدورات بواسطة قواسم العدد \(Q-1\).
لنكتب عدد الصفوف على الصورة \(r=m^4\)، وعدد الأعمدة على الصورة \(c=n^4\)، ثم نعرّف
$$Q=rc=(nm)^4,\qquad L=Q-1,\qquad \alpha=r=m^4.$$
بهذا تتحول المسألة كلها إلى دراسة البنية الدورية لتبديل معياري واحد.
خذ خلية تقع في الصف \(i\) والعمود \(j\)، حيث \(0\le i\lt r\) و\(0\le j\lt c\). فهرسها الخطي وفق row-major هو
$$x=ic+j,$$
أما فهرسها وفق column-major فهو
$$y=jr+i.$$
لنحسب الآن \(rx\):
$$rx=r(ic+j)=irc+rj=iQ+rj\equiv i+rj=y \pmod{Q-1}.$$
إذًا، لكل فهرس عدا الأخير لدينا
$$\pi(x)\equiv \alpha x \pmod L,\qquad 0\le x\lt L.$$
أما الفهرس المتبقي \(x=L=Q-1\) فهو نقطة ثابتة إضافية. كذلك فإن
$$L=(nm)^4-1\equiv -1 \pmod m$$
ومن ثم \(\gcd(\alpha,L)=1\)، أي إن الضرب في \(\alpha\) يعطي فعلًا تبديلًا على البواقي modulo \(L\).
إذا كان تبديل على \(Q\) عنصرًا يملك \(C\) دورة، فإن أقل عدد من عمليات التبديل اللازمة لتنفيذه يساوي \(Q-C\)، لأن الدورة ذات الطول \(t\) تحتاج بالضبط إلى \(t-1\) عملية تبديل. ولذلك تنحصر المسألة الآن في حساب عدد الدورات.
لكل \(x\in \mathbb{Z}/L\mathbb{Z}\) نعرّف
$$d=\frac{L}{\gcd(x,L)}.$$
هذا العدد \(d\) هو الرتبة الجمعية للعنصر \(x\) في الزمرة الدورية \(\mathbb{Z}/L\mathbb{Z}\). وبما أن \(\alpha\) قابل للعكس modulo \(L\)، فإن الضرب فيه لا يغيّر \(\gcd(x,L)\)، وبالتالي لا يغيّر \(d\) أيضًا. لذا ينقسم التبديل إلى طبقات ثابتة، طبقة لكل قاسم \(d\mid L\).
عدد البواقي التي رتبتها الجمعية تساوي \(d\) هو بالضبط \(\varphi(d)\)، لأنها مولدات الزمرة الجزئية الوحيدة ذات الحجم \(d\) داخل \(\mathbb{Z}/L\mathbb{Z}\).
اكتب
$$g=\gcd(x,L),\qquad x=gu,\qquad L=gd,$$
بحيث \(\gcd(u,d)=1\). عودة \(x\) إلى نفسه بعد \(t\) خطوات تعني
$$\alpha^t x\equiv x \pmod L.$$
وبالتعويض عن \(x=gu\) و\(L=gd\) نحصل على
$$gd\mid g(\alpha^t-1)u\iff d\mid(\alpha^t-1)u.$$
ولأن \(u\) قابل للعكس modulo \(d\)، فإن هذا يكافئ الشرط
$$\alpha^t\equiv 1 \pmod d.$$
إذًا طول كل مدار داخل الطبقة الموافقة لـ \(d\) هو
$$\operatorname{ord}_d(\alpha),$$
أي رتبة الضرب لـ \(\alpha\) modulo \(d\). وبما أن هذه الطبقة تحتوي \(\varphi(d)\) عنصرًا، فإن عدد الدورات التي تسهم بها هو
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.$$
بجمع مساهمات جميع القواسم نحصل على عدد الدورات داخل الجزء المعياري:
$$C_L=\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)},$$
مع الاتفاق على أن \(\operatorname{ord}_1(\alpha)=1\). هذا المجموع يحسب النقطة الثابتة \(x=0\) بالفعل، بينما يضيف الفهرس \(x=L=Q-1\) نقطة ثابتة أخرى خارج مجموعة البواقي، ولذلك يصبح العدد الكلي للدورات
$$C=C_L+1.$$
ومن ثم فإن عدد التبديلات للزوج \((n,m)\) هو
$$\boxed{W=Q-1-\sum_{d\mid L}\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}.}$$
مع أن المسألة الأصلية تستخدم أبعادًا من القوى الرابعة، فإن الآلية نفسها تظهر بوضوح في مستطيل صغير عادي له \(r=4\) صفوف و\(c=3\) أعمدة. في هذه الحالة
$$Q=12,\qquad L=11,\qquad \alpha=4,$$
ومن ثم على المجال \(0\le x\lt 11\) يكون
$$\pi(x)\equiv 4x \pmod{11}.$$
وبما أن قواسم \(11\) هي فقط \(1\) و\(11\)، نحصل على
$$C_{11}=1+\frac{\varphi(11)}{\operatorname{ord}_{11}(4)}=1+\frac{10}{5}=3.$$
وفعلًا تنقسم البواقي إلى الدورات
$$0,$$
$$1\to 4\to 5\to 9\to 3\to 1,$$
$$2\to 8\to 10\to 7\to 6\to 2,$$
ويكون الموضع الثاني عشر \(x=11\) نقطة ثابتة إضافية. لذلك فإن العدد الكلي للدورات يساوي \(4\)، ويكون أقل عدد من التبديلات
$$12-4=8.$$
وهذا هو المثال الصغير الذي تعتمد عليه التطبيقات للتحقق من صحة الصيغة.
إذا وضعنا \(s=nm\)، فإن
$$L=s^4-1=(s-1)(s+1)(s^2+1).$$
ولأن \(s\le 10^4\)، فإن الأعداد \(s-1\) و\(s+1\) و\(s^2+1\) تبقى متوسطة الحجم. لذا يكفي تحليل هذه الأعداد الثلاثة إلى عوامل أولية من أجل استعادة التحليل الكامل لـ \(L\).
لكل قوة أولية \(p^k\mid L\) لدينا
$$\operatorname{ord}_{p^k}(\alpha)\mid \varphi(p^k)=p^{k-1}(p-1).$$
تبدأ التطبيقات من القيمة \(\varphi(p^k)\)، ثم تزيل عواملها الأولية كلما ظل اختبار الأس المعياري
$$\alpha^{\,\varphi(p^k)/q}\equiv 1 \pmod{p^k}$$
صحيحًا.
وإذا كان
$$d=\prod_i p_i^{e_i},$$
فإن خاصية الضرب ومبرهنة البواقي الصينية تعطيان
$$\varphi(d)=\prod_i \varphi(p_i^{e_i}),\qquad \operatorname{ord}_d(\alpha)=\operatorname{lcm}_i\operatorname{ord}_{p_i^{e_i}}(\alpha).$$
ولهذا يكفي إجراء DFS على جميع الاختيارات \(0\le e_i\le v_{p_i}(L)\) لزيارة كل قاسم \(d\mid L\) وتجميع مساهمته الدقيقة، من غير أي حاجة إلى المرور المباشر على خلايا المستطيل وعددها \(Q\).
تتبع تطبيقات ++C وPython وJava الخطة العددية نفسها.
تُبنى أولًا غربال للأعداد الأولية مرة واحدة. ولكل زوج \((n,m)\)، تحسب الشيفرة \(s=nm\)، ثم تحلل \(s-1\) و\(s+1\) و\(s^2+1\)، وتدمج الأسس الناتجة للحصول على تحليل \(L=s^4-1\). ولأن أزواجًا مختلفة قد تعطي القيمة نفسها لـ \(s\)، فإن هذا التحليل يُخزَّن ويُعاد استعماله. كما تُخزَّن تحليلات الأعداد من الشكل \(p-1\)، لأنها تُستخدم مرارًا عند تقليص \(\varphi(p^k)\) إلى الرتبة الدقيقة \(\operatorname{ord}_{p^k}(\alpha)\).
لكل قوة أولية \(p^k\mid L\)، تُحسب مسبقًا القيمتان \(\varphi(p^k)\) و\(\operatorname{ord}_{p^k}(\alpha)\). بعد ذلك تُجرى DFS على القواسم: في كل مستوى من الاستدعاء الذاتي يُختار أس لأحد الأعداد الأولية، ويُضرب المساهم الجاري من \(\varphi\)، ثم تُحدَّث الرتبة الحالية باستخدام \(\operatorname{lcm}\)، ويستمر النزول. وعند كل ورقة تُضاف الكمية
$$\frac{\varphi(d)}{\operatorname{ord}_d(\alpha)}$$
إلى مجموع الدورات \(C_L\). لذلك تكون القيمة المعادة لعدد التبديلات هي \(Q-1-C_L\).
ثم تجمع الحلقات الخارجية هذه النتيجة على جميع الأزواج \(2\le n\le m\le 100\). كذلك تقارن التطبيقات الصيغة مع تفكيك صريح للدورات في الحالات الصغيرة؛ فالمستطيل العادي \(3\times 4\) يعطي بالضبط \(8\) تبديلات، وهو ما يطابق النظرية تمامًا.
بالنسبة إلى زوج واحد \((n,m)\)، لا تمر الخوارزمية أبدًا على جميع المواضع وعددها \(Q=(nm)^4\). يتركز العمل في تحليل \(s-1\) و\(s+1\) و\(s^2+1\) إلى عوامل أولية، وحساب رتب الضرب على القوى الأولية المناسبة، ثم تعداد قواسم \(L\) وعددها \(\tau(L)\) بواسطة DFS على أسس العوامل الأولية. عمليًا هذا أصغر بكثير من تفكيك التبديل الكامل إلى دورات بطريقة مباشرة.
أما الذاكرة فتبقى معتدلة؛ إذ تهيمن عليها قائمة الأوليات، وذاكرات التخزين المؤقت لتحليلات العوامل، والجداول الخاصة بالقوى الأولية للزوج الحالي. وتأتي الكفاءة من أن الحساب يتعامل مع تحليل \(L=(nm)^4-1\) لا مع \((nm)^4\) خلية منفردة.