For each modulus \(m \gt 1\), consider linear maps
$$f(x)\equiv ax+b \pmod{m},\qquad 0 \lt a \lt m,\quad 0\le b \lt m.$$
The map is a retraction when it is idempotent on every residue class:
$$f(f(x))\equiv f(x)\pmod{m}\qquad\text{for all }x.$$
Let \(R(m)\) be the number of such maps. Problem 446 asks for
$$F(N)=\sum_{n=1}^{N}R(n^4+4),$$
with the checkpoint \(F(1024)=77532377300600\). The challenge is to evaluate \(F(10^7)\bmod(10^9+7)\) without factoring each number \(n^4+4\) independently.
Composing the map once more gives
$$f(f(x))\equiv a(ax+b)+b\equiv a^2x+ab+b \pmod{m}.$$
For this to equal \(ax+b\) for every \(x\), both the coefficient of \(x\) and the constant correction must vanish modulo \(m\). Therefore
$$m\mid a(a-1),\qquad m\mid ab.$$
Write
$$m=\prod_{i=1}^{r}p_i^{e_i}.$$
Because \(\gcd(a,a-1)=1\), each prime power \(p_i^{e_i}\) must divide exactly one of \(a\) or \(a-1\). Hence for every \(p_i^{e_i}\parallel m\),
$$a\equiv 0 \pmod{p_i^{e_i}}\qquad\text{or}\qquad a\equiv 1 \pmod{p_i^{e_i}}.$$
These independent choices correspond to the unitary divisors of \(m\). If we define
$$d=\gcd(a,m),$$
then \(d\mid m\) and \(\gcd(d,m/d)=1\), so \(d\) is unitary. Conversely, every unitary divisor \(d \lt m\) determines one admissible residue class for \(a\).
Now fix such an \(a\), and write
$$a=d\,a_1,\qquad m=d\,m_1,\qquad \gcd(a_1,m_1)=1.$$
The condition \(m\mid ab\) becomes
$$d\,m_1\mid d\,a_1b \iff m_1\mid a_1b \iff m_1\mid b,$$
because \(a_1\) is invertible modulo \(m_1\). Among the residues \(0\le b\lt m=d\,m_1\), exactly \(d\) are multiples of \(m_1\). Therefore each admissible \(a\) contributes exactly \(d\) values of \(b\).
Summing over all unitary divisors gives
$$R(m)=\sum_{\substack{d\parallel m\\ d \lt m}} d=\left(\sum_{d\parallel m}d\right)-m.$$
Thus
$$\boxed{R(m)=\sigma^*(m)-m},$$
where \(\sigma^*(m)\) is the sum of unitary divisors. If \(m=\prod p^e\), then
$$\sigma^*(m)=\prod_{p^e\parallel m}(1+p^e).$$
The key algebraic identity is the Sophie Germain factorization
$$n^4+4=(n^2-2n+2)(n^2+2n+2).$$
It is convenient to write
$$A_n=(n-1)^2+1,\qquad B_n=(n+1)^2+1,$$
so that
$$n^4+4=A_nB_n.$$
Define also
$$Q(m)=\sigma^*(m^2+1).$$
Then \(A_n\) and \(B_n\) are exactly the values \(m^2+1\) at \(m=n-1\) and \(m=n+1\). The whole problem reduces to precomputing \(Q(m)\) for \(0\le m\le N+1\).
Any common divisor \(g\) of \(A_n\) and \(B_n\) must divide their difference:
$$g\mid (B_n-A_n)=4n.$$
Also
$$A_n\equiv B_n\equiv 2 \pmod{n}.$$
If an odd prime \(p\) divided both \(A_n\) and \(B_n\), then from \(p\mid 4n\) we would get \(p\mid n\), but then \(A_n\equiv 2\pmod p\), which is impossible. So the gcd can only be a power of \(2\).
If \(n\) is odd, then \(n-1\) and \(n+1\) are even, hence \(A_n\) and \(B_n\) are odd, so
$$\gcd(A_n,B_n)=1.$$
If \(n\) is even, then \(n-1\) and \(n+1\) are odd, so
$$A_n\equiv B_n\equiv 2 \pmod{8}.$$
Therefore each factor contains exactly one power of \(2\), and
$$\gcd(A_n,B_n)=2.$$
When \(n\) is odd, the factors \(A_n\) and \(B_n\) are coprime, and \(\sigma^*\) is multiplicative on coprime inputs. Hence
$$\sigma^*(n^4+4)=\sigma^*(A_n)\sigma^*(B_n)=Q(n-1)Q(n+1).$$
When \(n\) is even, write
$$A_n=2u,\qquad B_n=2v,$$
with \(u\) and \(v\) odd and coprime. Then
$$Q(n-1)=\sigma^*(2u)=(1+2)\sigma^*(u)=3\sigma^*(u),$$
$$Q(n+1)=\sigma^*(2v)=3\sigma^*(v).$$
But now
$$n^4+4=A_nB_n=4uv,$$
and since \(4\), \(u\), and \(v\) are pairwise coprime,
$$\sigma^*(n^4+4)=\sigma^*(4)\sigma^*(u)\sigma^*(v)=5\sigma^*(u)\sigma^*(v).$$
Comparing the two expressions yields the constant correction
$$\sigma^*(n^4+4)=\frac{5}{9}Q(n-1)Q(n+1)\qquad(n\text{ even}).$$
So the final closed form is
$$\boxed{\sigma^*(n^4+4)= \begin{cases} Q(n-1)Q(n+1), & n\text{ odd},\\[4pt] \dfrac{5}{9}Q(n-1)Q(n+1), & n\text{ even}. \end{cases}}$$
For an odd prime \(p\) to divide \(m^2+1\), we must have
$$m^2\equiv -1 \pmod{p}.$$
That means \(-1\) is a quadratic residue modulo \(p\), which happens only for
$$p\equiv 1 \pmod{4}.$$
The prime \(2\) is special: \(2\mid m^2+1\) exactly when \(m\) is odd, and then \(m^2+1\equiv 2\pmod 8\), so the exponent of \(2\) is exactly \(1\).
This leads to a quadratic-congruence sieve:
For \(p=2\), update all odd \(m\).
For each odd prime \(p\equiv 1\pmod 4\), find one square root \(r\) of \(-1\) modulo \(p\). Then the only possible indices are the two residue classes
$$m\equiv r \pmod p,\qquad m\equiv -r \pmod p.$$
For every such \(m\), divide \(m^2+1\) by \(p\) repeatedly to recover the exact exponent \(p^e\parallel (m^2+1)\), and multiply the running value of \(Q(m)\) by \(1+p^e\).
After all relevant primes up to \(N+1\) have been processed, any remaining factor larger than \(1\) must itself be prime. Indeed, two unfactored primes both exceeding \(N+1\) would have product larger than \((N+1)^2+1\), but \(m^2+1\le (N+1)^2+1\). So one final factor \(1+\text{leftover}\) completes \(Q(m)\).
For \(n=2\), we have
$$n^4+4=20,\qquad A_2=2,\qquad B_2=10.$$
Thus
$$Q(1)=\sigma^*(2)=3,\qquad Q(3)=\sigma^*(10)=(1+2)(1+5)=18.$$
Since \(n\) is even,
$$\sigma^*(20)=\frac{5}{9}\cdot 3\cdot 18=30,$$
and therefore
$$R(20)=30-20=10.$$
For \(n=3\), the factors are coprime:
$$n^4+4=85,\qquad A_3=5,\qquad B_3=17.$$
Hence
$$\sigma^*(85)=Q(2)Q(4)=\sigma^*(5)\sigma^*(17)=6\cdot 18=108,$$
so
$$R(85)=108-85=23.$$
The C++, Python, and Java implementations allocate arrays for the unfactored remainder of \(m^2+1\) and for the running value of \(Q(m)\) modulo \(10^9+7\), for every \(0\le m\le N+1\). Including \(m=0\) makes the first summand \(n=1\) work without a special case, since \(0^2+1=1\) and \(Q(0)=1\).
They next build a prime table up to \(N+1\). The prime \(2\) is handled by scanning odd indices. For each odd prime \(p\equiv 1\pmod 4\), the implementation computes a square root of \(-1\) modulo \(p\) with the Tonelli-Shanks algorithm, then walks both arithmetic progressions \(r,r+p,r+2p,\dots\) and \(-r,-r+p,-r+2p,\dots\).
Whenever an index is hit, the implementation strips the full \(p\)-adic exponent from the current remainder and multiplies the running unitary-divisor product by \(1+p^e\). After the sieve phase, any leftover prime factor is inserted once more. Finally, for each \(n\), the code combines the two precomputed values at \(n-1\) and \(n+1\), applies the \(5/9\) adjustment when \(n\) is even, subtracts \(n^4+4\) modulo \(10^9+7\), and accumulates the result.
The prime preprocessing and the arrays over \(0,\dots,N+1\) use \(O(N)\) memory. The residue-class sweeps visit about \(2N/p\) indices for each prime \(p\equiv 1\pmod 4\), so the total work is near
$$\sum_{p\le N+1,\ p\equiv 1\!\!\!\pmod 4}\frac{N}{p}=O(N\log\log N)$$
in practice. The remaining arithmetic per visited index is constant apart from stripping a prime power, so the overall method runs in near \(O(N\log\log N)\) time and \(O(N)\) memory.
Zu jedem Modul \(m \gt 1\) betrachten wir lineare Abbildungen
$$f(x)\equiv ax+b \pmod{m},\qquad 0 \lt a \lt m,\quad 0\le b \lt m.$$
Die Abbildung ist eine Retraktion, wenn sie auf allen Restklassen idempotent ist:
$$f(f(x))\equiv f(x)\pmod{m}\qquad\text{fur alle }x.$$
Sei \(R(m)\) die Anzahl solcher Abbildungen. In Problem 446 ist
$$F(N)=\sum_{n=1}^{N}R(n^4+4)$$
zu berechnen. Als Kontrollwert ist \(F(1024)=77532377300600\) gegeben. Die eigentliche Schwierigkeit besteht darin, \(F(10^7)\bmod(10^9+7)\) zu bestimmen, ohne jedes \(n^4+4\) separat zu faktorisieren.
Durch nochmaliges Einsetzen erhalt man
$$f(f(x))\equiv a(ax+b)+b\equiv a^2x+ab+b \pmod{m}.$$
Damit dies fur alle \(x\) mit \(ax+b\) ubereinstimmt, mussen sowohl der lineare als auch der konstante Zusatzterm modulo \(m\) verschwinden. Also gilt
$$m\mid a(a-1),\qquad m\mid ab.$$
Schreibe
$$m=\prod_{i=1}^{r}p_i^{e_i}.$$
Da \(\gcd(a,a-1)=1\) ist, muss jede Primzahlpotenz \(p_i^{e_i}\) genau einen der beiden Faktoren teilen. Fur jedes \(p_i^{e_i}\parallel m\) folgt daher
$$a\equiv 0 \pmod{p_i^{e_i}}\qquad\text{oder}\qquad a\equiv 1 \pmod{p_i^{e_i}}.$$
Diese unabhangigen Entscheidungen entsprechen den unitaren Teilern von \(m\). Mit
$$d=\gcd(a,m)$$
gilt namlich \(d\mid m\) und \(\gcd(d,m/d)=1\). Umgekehrt liefert jeder unitare Teiler \(d \lt m\) genau eine zulassige Restklasse fur \(a\).
Fixiere nun ein solches \(a\) und schreibe
$$a=d\,a_1,\qquad m=d\,m_1,\qquad \gcd(a_1,m_1)=1.$$
Dann wird aus \(m\mid ab\)
$$d\,m_1\mid d\,a_1b \iff m_1\mid a_1b \iff m_1\mid b,$$
weil \(a_1\) modulo \(m_1\) invertierbar ist. Unter den Resten \(0\le b\lt m=d\,m_1\) gibt es genau \(d\) Vielfache von \(m_1\). Also tragt jedes zulassige \(a\) genau \(d\) Werte von \(b\) bei.
Summiert uber alle unitaren Teiler ergibt das
$$R(m)=\sum_{\substack{d\parallel m\\ d \lt m}} d=\left(\sum_{d\parallel m}d\right)-m.$$
Damit folgt
$$\boxed{R(m)=\sigma^*(m)-m},$$
wobei \(\sigma^*(m)\) die Summe der unitaren Teiler ist. Fur \(m=\prod p^e\) gilt
$$\sigma^*(m)=\prod_{p^e\parallel m}(1+p^e).$$
Die zentrale Identitat ist die Sophie-Germain-Zerlegung
$$n^4+4=(n^2-2n+2)(n^2+2n+2).$$
Wir setzen
$$A_n=(n-1)^2+1,\qquad B_n=(n+1)^2+1,$$
sodass
$$n^4+4=A_nB_n.$$
Weiter definieren wir
$$Q(m)=\sigma^*(m^2+1).$$
Dann sind \(A_n\) und \(B_n\) genau die Werte von \(m^2+1\) fur \(m=n-1\) beziehungsweise \(m=n+1\). Also genugt es, alle \(Q(m)\) fur \(0\le m\le N+1\) vorzuberechnen.
Jeder gemeinsame Teiler \(g\) von \(A_n\) und \(B_n\) teilt auch ihre Differenz:
$$g\mid (B_n-A_n)=4n.$$
Außerdem gilt
$$A_n\equiv B_n\equiv 2 \pmod{n}.$$
Wurde eine ungerade Primzahl \(p\) beide Faktoren teilen, so folgte aus \(p\mid 4n\) auch \(p\mid n\). Dann ware aber \(A_n\equiv 2\pmod p\), also ein Widerspruch. Der ggT kann daher nur eine Zweierpotenz sein.
Ist \(n\) ungerade, dann sind \(n-1\) und \(n+1\) gerade und damit \(A_n\) und \(B_n\) beide ungerade. Also
$$\gcd(A_n,B_n)=1.$$
Ist \(n\) gerade, dann sind \(n-1\) und \(n+1\) ungerade und somit
$$A_n\equiv B_n\equiv 2 \pmod{8}.$$
Jeder Faktor enthalt also genau einen Faktor \(2\), und damit
$$\gcd(A_n,B_n)=2.$$
Fur ungerades \(n\) sind \(A_n\) und \(B_n\) teilerfremd. Da \(\sigma^*\) auf teilerfremden Zahlen multiplikativ ist, folgt
$$\sigma^*(n^4+4)=\sigma^*(A_n)\sigma^*(B_n)=Q(n-1)Q(n+1).$$
Fur gerades \(n\) schreiben wir
$$A_n=2u,\qquad B_n=2v,$$
wobei \(u\) und \(v\) ungerade und teilerfremd sind. Dann ist
$$Q(n-1)=\sigma^*(2u)=3\sigma^*(u),$$
$$Q(n+1)=\sigma^*(2v)=3\sigma^*(v).$$
Außerdem gilt
$$n^4+4=A_nB_n=4uv,$$
und wegen der Paarweise-Teilerfremdheit von \(4\), \(u\) und \(v\) erhalten wir
$$\sigma^*(n^4+4)=\sigma^*(4)\sigma^*(u)\sigma^*(v)=5\sigma^*(u)\sigma^*(v).$$
Vergleicht man beide Darstellungen, ergibt sich der feste Korrekturfaktor
$$\sigma^*(n^4+4)=\frac{5}{9}Q(n-1)Q(n+1)\qquad(n\text{ gerade}).$$
Damit lautet die geschlossene Formel
$$\boxed{\sigma^*(n^4+4)= \begin{cases} Q(n-1)Q(n+1), & n\text{ ungerade},\\[4pt] \dfrac{5}{9}Q(n-1)Q(n+1), & n\text{ gerade}. \end{cases}}$$
Damit eine ungerade Primzahl \(p\) den Wert \(m^2+1\) teilt, muss
$$m^2\equiv -1 \pmod p$$
gelten. Also ist \(-1\) ein quadratischer Rest modulo \(p\), was nur fur
$$p\equiv 1 \pmod 4$$
moglich ist. Die Primzahl \(2\) ist der Sonderfall: \(2\mid m^2+1\) genau dann, wenn \(m\) ungerade ist, und dann ist der Zweierexponent exakt \(1\).
Daraus entsteht ein Sieb uber quadratische Kongruenzen:
Fur \(p=2\) werden alle ungeraden \(m\) aktualisiert.
Fur jede ungerade Primzahl \(p\equiv 1\pmod 4\) wird eine Losung \(r\) von \(x^2\equiv -1\pmod p\) bestimmt. Die einzig moglichen Indizes liegen dann in den beiden Restklassen
$$m\equiv r \pmod p,\qquad m\equiv -r \pmod p.$$
Fur jedes solche \(m\) wird \(m^2+1\) so oft durch \(p\) geteilt, bis die genaue Potenz \(p^e\parallel (m^2+1)\) gefunden ist, und der laufende Wert von \(Q(m)\) wird mit \(1+p^e\) multipliziert.
Nachdem alle relevanten Primzahlen bis \(N+1\) abgearbeitet sind, kann ein Restfaktor groser als \(1\) nur noch selbst prim sein. Zwei unfaktorisierte Primzahlen, beide groser als \(N+1\), hatten namlich ein Produkt groser als \((N+1)^2+1\), wahrend stets \(m^2+1\le (N+1)^2+1\) gilt. Genau dieser Rest liefert den letzten Faktor \(1+\text{Rest}\).
Fur \(n=2\) gilt
$$n^4+4=20,\qquad A_2=2,\qquad B_2=10.$$
Daher
$$Q(1)=\sigma^*(2)=3,\qquad Q(3)=\sigma^*(10)=(1+2)(1+5)=18.$$
Weil \(n\) gerade ist, folgt
$$\sigma^*(20)=\frac{5}{9}\cdot 3\cdot 18=30,$$
also
$$R(20)=30-20=10.$$
Fur \(n=3\) sind die Faktoren teilerfremd:
$$n^4+4=85,\qquad A_3=5,\qquad B_3=17.$$
Damit
$$\sigma^*(85)=Q(2)Q(4)=\sigma^*(5)\sigma^*(17)=6\cdot 18=108,$$
und somit
$$R(85)=108-85=23.$$
Die Implementierungen in C++, Python und Java legen fur alle \(0\le m\le N+1\) ein Feld fur den noch unfaktorisierten Rest von \(m^2+1\) und ein zweites Feld fur den laufenden Wert von \(Q(m)\) modulo \(10^9+7\) an. Durch die Aufnahme von \(m=0\) wird auch der erste Summand \(n=1\) ohne Sonderfall behandelt, denn \(0^2+1=1\) und damit \(Q(0)=1\).
Anschließend wird eine Primtabelle bis \(N+1\) aufgebaut. Die Primzahl \(2\) wird uber alle ungeraden Indizes verarbeitet. Fur jede ungerade Primzahl \(p\equiv 1\pmod 4\) berechnet die Implementierung mit Tonelli-Shanks eine Quadratwurzel von \(-1\) modulo \(p\) und lauft dann beide arithmetischen Progressionen \(r,r+p,r+2p,\dots\) sowie \(-r,-r+p,-r+2p,\dots\) ab.
Wann immer ein Index getroffen wird, entfernt die Implementierung die volle \(p\)-adische Potenz aus dem aktuellen Rest und multipliziert das laufende unitare Teilerprodukt mit \(1+p^e\). Nach dem Sieb wird ein moglicher Restfaktor noch einmal eingetragen. Zum Schluss werden fur jedes \(n\) die vorberechneten Werte bei \(n-1\) und \(n+1\) kombiniert, fur gerades \(n\) mit dem Faktor \(5/9\) korrigiert, \(n^4+4\) modulo \(10^9+7\) subtrahiert und alles aufsummiert.
Die Primvorbereitung und die Arrays uber \(0,\dots,N+1\) benotigen \(O(N)\) Speicher. Die Restklassensiebe besuchen fur jede Primzahl \(p\equiv 1\pmod 4\) ungefahr \(2N/p\) Indizes, sodass die Gesamtkosten praktisch nahe bei
$$\sum_{p\le N+1,\ p\equiv 1\!\!\!\pmod 4}\frac{N}{p}=O(N\log\log N)$$
liegen. Die zusatzliche Arbeit pro Treffer ist konstant bis auf das Entfernen einer Primzahlpotenz. Insgesamt arbeitet das Verfahren daher in nahe \(O(N\log\log N)\) Zeit und \(O(N)\) Speicher.
Her \(m \gt 1\) modulu icin su dogrusal fonksiyonlari ele alalim:
$$f(x)\equiv ax+b \pmod{m},\qquad 0 \lt a \lt m,\quad 0\le b \lt m.$$
Fonksiyon, tum kalan siniflarinda idempotent ise bir geri cekimdir:
$$f(f(x))\equiv f(x)\pmod{m}\qquad\text{tum }x\text{ icin}.$$
\(R(m)\), bu kosulu saglayan fonksiyonlarin sayisi olsun. Problem 446'da istenen toplam
$$F(N)=\sum_{n=1}^{N}R(n^4+4)$$
seklindedir. Kontrol degeri \(F(1024)=77532377300600\) olarak verilir. Asil hedef, her \(n^4+4\) sayisini ayri ayri carpanlara ayirmadan \(F(10^7)\bmod(10^9+7)\) degerine ulasmaktir.
Fonksiyonu bir kez daha uygulayalim:
$$f(f(x))\equiv a(ax+b)+b\equiv a^2x+ab+b \pmod{m}.$$
Bunun her \(x\) icin \(ax+b\)'ye esit olmasi icin hem \(x\)'in katsayisi hem de sabit duzeltme terimi modulo \(m\) sifir olmalidir. Dolayisiyla
$$m\mid a(a-1),\qquad m\mid ab.$$
\(m\)'yi
$$m=\prod_{i=1}^{r}p_i^{e_i}$$
seklinde yazalim. \(\gcd(a,a-1)=1\) oldugu icin her asal kuvvet \(p_i^{e_i}\), bu iki carpandan tam olarak birini bolmek zorundadir. Bu nedenle her \(p_i^{e_i}\parallel m\) icin
$$a\equiv 0 \pmod{p_i^{e_i}}\qquad\text{veya}\qquad a\equiv 1 \pmod{p_i^{e_i}}$$
olur. Bu bagimsiz secimler, \(m\)'nin uniter bolenleriyle birebir eslestirilir. Gercekten,
$$d=\gcd(a,m)$$
alindiginda \(d\mid m\) ve \(\gcd(d,m/d)=1\) olur. Tersine, \(d \lt m\) olan her uniter bolen tek bir uygun \(a\) kalani verir.
Simdi bu tur bir \(a\) sabitleyip
$$a=d\,a_1,\qquad m=d\,m_1,\qquad \gcd(a_1,m_1)=1$$
yazalim. O zaman \(m\mid ab\) kosulu
$$d\,m_1\mid d\,a_1b \iff m_1\mid a_1b \iff m_1\mid b$$
haline gelir; cunku \(a_1\), \(m_1\) modunda tersinirdir. \(0\le b\lt m=d\,m_1\) araliginda \(m_1\)'in tam olarak \(d\) kati vardir. Yani her uygun \(a\), tam \(d\) farkli \(b\) uretir.
Boylece tum uniter bolenler uzerinden toplarsak
$$R(m)=\sum_{\substack{d\parallel m\\ d \lt m}} d=\left(\sum_{d\parallel m}d\right)-m$$
elde edilir. Sonuc olarak
$$\boxed{R(m)=\sigma^*(m)-m},$$
burada \(\sigma^*(m)\) uniter bolenlerin toplami demektir. Eger \(m=\prod p^e\) ise
$$\sigma^*(m)=\prod_{p^e\parallel m}(1+p^e)$$
olur.
Kilit cebirsel ozdeslik Sophie Germain carpanlasmasidir:
$$n^4+4=(n^2-2n+2)(n^2+2n+2).$$
Su tanimlari yapalim:
$$A_n=(n-1)^2+1,\qquad B_n=(n+1)^2+1,$$
boylece
$$n^4+4=A_nB_n.$$
Ayrica
$$Q(m)=\sigma^*(m^2+1)$$
olsun. O halde \(A_n\) ve \(B_n\), sirasiyla \(m=n-1\) ve \(m=n+1\) icin ortaya cikan \(m^2+1\) degerleridir. Bu nedenle butun is, \(0\le m\le N+1\) araligindaki \(Q(m)\) degerlerini topluca hesaplamaya doner.
\(A_n\) ve \(B_n\)'nin her ortak boleni farklarini da boler:
$$g\mid (B_n-A_n)=4n.$$
Diger yandan
$$A_n\equiv B_n\equiv 2 \pmod{n}.$$
Eger tek bir asal \(p\), her iki carpani da bolseydi, \(p\mid 4n\) oldugundan \(p\mid n\) da olurdu. Fakat bu durumda \(A_n\equiv 2\pmod p\) olur; bu imkansizdir. Demek ki ortak bolen sadece \(2\)'nin kuvveti olabilir.
\(n\) tekse, \(n-1\) ve \(n+1\) cifttir; dolayisiyla \(A_n\) ve \(B_n\) tektir. Bu durumda
$$\gcd(A_n,B_n)=1.$$
\(n\) ciftse, \(n-1\) ve \(n+1\) tektir ve bu nedenle
$$A_n\equiv B_n\equiv 2 \pmod{8}.$$
Her iki carpanda da \(2\)'nin ussu tam olarak \(1\)'dir; dolayisiyla
$$\gcd(A_n,B_n)=2.$$
\(n\) tek oldugunda \(A_n\) ile \(B_n\) aralarinda asaldir. \(\sigma^*\) aralarinda asal sayilarda carpimsal oldugu icin
$$\sigma^*(n^4+4)=\sigma^*(A_n)\sigma^*(B_n)=Q(n-1)Q(n+1).$$
\(n\) cift oldugunda ise
$$A_n=2u,\qquad B_n=2v$$
seklinde yazabiliriz; burada \(u\) ve \(v\) tektir ve aralarinda asaldir. O zaman
$$Q(n-1)=\sigma^*(2u)=3\sigma^*(u),$$
$$Q(n+1)=\sigma^*(2v)=3\sigma^*(v).$$
Ayrica
$$n^4+4=A_nB_n=4uv,$$
ve \(4\), \(u\), \(v\) ciftler halinde aralarinda asal oldugundan
$$\sigma^*(n^4+4)=\sigma^*(4)\sigma^*(u)\sigma^*(v)=5\sigma^*(u)\sigma^*(v).$$
Iki ifadeyi karsilastirinca sabit duzeltme katsayisi ortaya cikar:
$$\sigma^*(n^4+4)=\frac{5}{9}Q(n-1)Q(n+1)\qquad(n\text{ cift}).$$
Son kapali form sunlardir:
$$\boxed{\sigma^*(n^4+4)= \begin{cases} Q(n-1)Q(n+1), & n\text{ tek},\\[4pt] \dfrac{5}{9}Q(n-1)Q(n+1), & n\text{ cift}. \end{cases}}$$
Tek bir asal \(p\)'nin \(m^2+1\)'i bolmesi icin
$$m^2\equiv -1 \pmod p$$
olmalidir. Bu da \(-1\)'in modulo \(p\)'de kuadratik kalan olmasi demektir; bu ancak
$$p\equiv 1 \pmod 4$$
oldugunda gerceklestir. \(2\) asalinin durumu ozel: \(2\mid m^2+1\) tam olarak \(m\) tekken olur ve o zaman da \(2\)'nin ussu sadece \(1\)'dir.
Bundan bir kuadratik kongruens elemesi dogar:
\(p=2\) icin tum tek \(m\) degerleri guncellenir.
Her \(p\equiv 1\pmod 4\) asalinda once \(x^2\equiv -1\pmod p\) denkleminin bir koku \(r\) bulunur. O zaman olasi indisler yalnizca su iki kalan sinifidir:
$$m\equiv r \pmod p,\qquad m\equiv -r \pmod p.$$
Bu siniflardaki her \(m\) icin \(m^2+1\) sayisi \(p\)'ye bolunebildigi kadar bolunur; boylece tam us \(p^e\parallel (m^2+1)\) elde edilir ve \(Q(m)\) degeri \(1+p^e\) ile carpilir.
Ilgili tum asallar \(N+1\)'e kadar islendikten sonra \(1\)'den buyuk kalan faktor ancak tek bir asal olabilir. Cunku ikisi de \(N+1\)'den buyuk iki asal kalsaydi carpanlari \((N+1)^2+1\)'den buyuk olurdu; oysa her zaman \(m^2+1\le (N+1)^2+1\) vardir. Bu son parca da \(1+\text{kalan}\) carpanini verir.
\(n=2\) icin
$$n^4+4=20,\qquad A_2=2,\qquad B_2=10.$$
Dolayisiyla
$$Q(1)=\sigma^*(2)=3,\qquad Q(3)=\sigma^*(10)=(1+2)(1+5)=18.$$
\(n\) cift oldugundan
$$\sigma^*(20)=\frac{5}{9}\cdot 3\cdot 18=30,$$
ve buradan
$$R(20)=30-20=10$$
gelir.
\(n=3\) icin carpanlar aralarinda asaldir:
$$n^4+4=85,\qquad A_3=5,\qquad B_3=17.$$
Bu nedenle
$$\sigma^*(85)=Q(2)Q(4)=\sigma^*(5)\sigma^*(17)=6\cdot 18=108,$$
dolayisiyla
$$R(85)=108-85=23.$$
C++, Python ve Java uygulamalari, \(0\le m\le N+1\) araligindaki her deger icin bir yandan \(m^2+1\)'in henuz ayrilmamis kalani, diger yandan da \(Q(m)\)'nin \(10^9+7\) modundaki degeri icin diziler kurar. \(m=0\)'in dahil edilmesi sayesinde ilk terim olan \(n=1\) de ozel durum gerektirmez; cunku \(0^2+1=1\) ve \(Q(0)=1\) olur.
Daha sonra \(N+1\)'e kadar asallar bulunur. \(2\) asalinin katkisi tum tek indisler taranarak eklenir. Her \(p\equiv 1\pmod 4\) asali icin uygulama Tonelli-Shanks algoritmasi ile \(-1\)'in bir karekokunu bulur ve ardindan \(r,r+p,r+2p,\dots\) ile \(-r,-r+p,-r+2p,\dots\) aritmetik dizilerini gezer.
Bir indis isabet aldiginda, ilgili kalan sayidan \(p\)'nin tam kuvveti soyulur ve calisan uniter bolen carpimina \(1+p^e\) carpanı eklenir. Eleme bittikten sonra varsa kalan asal da bir kez daha eklenir. Son dongude her \(n\) icin \(n-1\) ve \(n+1\) konumlarindaki degerler carpilir, \(n\) ciftse \(5/9\) duzeltmesi uygulanir, \(n^4+4\) moduler olarak cikarilir ve toplam olusturulur.
Asal onislemesi ve \(0,\dots,N+1\) uzerindeki diziler \(O(N)\) bellek kullanir. Kalan sinifi taramalari, her \(p\equiv 1\pmod 4\) asali icin yaklasik \(2N/p\) indis ziyaret eder; bu da pratikte
$$\sum_{p\le N+1,\ p\equiv 1\!\!\!\pmod 4}\frac{N}{p}=O(N\log\log N)$$
buyuklugune karsilik gelir. Her ziyaretteki ek is, bir asal kuvvetin soyulmasi disinda sabittir. Sonuc olarak yontem yaklasik \(O(N\log\log N)\) zaman ve \(O(N)\) bellek ister.
Para cada modulo \(m \gt 1\), consideramos las aplicaciones lineales
$$f(x)\equiv ax+b \pmod{m},\qquad 0 \lt a \lt m,\quad 0\le b \lt m.$$
La aplicacion es una retraccion si es idempotente en todas las clases residuales:
$$f(f(x))\equiv f(x)\pmod{m}\qquad\text{para todo }x.$$
Sea \(R(m)\) el numero de tales aplicaciones. En el problema 446 se pide
$$F(N)=\sum_{n=1}^{N}R(n^4+4),$$
con el punto de control \(F(1024)=77532377300600\). La dificultad real es calcular \(F(10^7)\bmod(10^9+7)\) sin factorizar por separado cada numero \(n^4+4\).
Al componer una vez mas, obtenemos
$$f(f(x))\equiv a(ax+b)+b\equiv a^2x+ab+b \pmod{m}.$$
Para que esto coincida con \(ax+b\) para todo \(x\), deben anularse modulo \(m\) tanto el coeficiente de \(x\) como la correccion constante. Por tanto,
$$m\mid a(a-1),\qquad m\mid ab.$$
Escribamos
$$m=\prod_{i=1}^{r}p_i^{e_i}.$$
Como \(\gcd(a,a-1)=1\), cada potencia prima \(p_i^{e_i}\) debe dividir exactamente a uno de los factores \(a\) o \(a-1\). Asi, para cada \(p_i^{e_i}\parallel m\),
$$a\equiv 0 \pmod{p_i^{e_i}}\qquad\text{o}\qquad a\equiv 1 \pmod{p_i^{e_i}}.$$
Estas decisiones independientes corresponden a los divisores unitarios de \(m\). Si definimos
$$d=\gcd(a,m),$$
entonces \(d\mid m\) y \(\gcd(d,m/d)=1\). Reciprocamente, todo divisor unitario \(d \lt m\) determina una clase valida de \(a\).
Fijemos ahora un \(a\) admisible y escribamos
$$a=d\,a_1,\qquad m=d\,m_1,\qquad \gcd(a_1,m_1)=1.$$
La condicion \(m\mid ab\) se convierte en
$$d\,m_1\mid d\,a_1b \iff m_1\mid a_1b \iff m_1\mid b,$$
porque \(a_1\) es invertible modulo \(m_1\). Entre los residuos \(0\le b\lt m=d\,m_1\), exactamente \(d\) son multiplos de \(m_1\). Por eso, cada \(a\) admisible aporta exactamente \(d\) valores de \(b\).
Sumando sobre todos los divisores unitarios, resulta
$$R(m)=\sum_{\substack{d\parallel m\\ d \lt m}} d=\left(\sum_{d\parallel m}d\right)-m.$$
En consecuencia,
$$\boxed{R(m)=\sigma^*(m)-m},$$
donde \(\sigma^*(m)\) es la suma de divisores unitarios. Si \(m=\prod p^e\), entonces
$$\sigma^*(m)=\prod_{p^e\parallel m}(1+p^e).$$
La identidad algebraica clave es la factorizacion de Sophie Germain:
$$n^4+4=(n^2-2n+2)(n^2+2n+2).$$
Definimos
$$A_n=(n-1)^2+1,\qquad B_n=(n+1)^2+1,$$
de modo que
$$n^4+4=A_nB_n.$$
Tambien definimos
$$Q(m)=\sigma^*(m^2+1).$$
Asi, \(A_n\) y \(B_n\) son exactamente los valores \(m^2+1\) en \(m=n-1\) y \(m=n+1\). El problema entero pasa a ser el calculo conjunto de \(Q(m)\) para \(0\le m\le N+1\).
Cualquier divisor comun \(g\) de \(A_n\) y \(B_n\) debe dividir la diferencia
$$g\mid (B_n-A_n)=4n.$$
Ademas,
$$A_n\equiv B_n\equiv 2 \pmod{n}.$$
Si un primo impar \(p\) dividiera a ambos factores, entonces de \(p\mid 4n\) se deduciria \(p\mid n\), pero en ese caso \(A_n\equiv 2\pmod p\), contradiccion. Por lo tanto, el mcd solo puede ser una potencia de \(2\).
Si \(n\) es impar, entonces \(n-1\) y \(n+1\) son pares, y por eso \(A_n\) y \(B_n\) son impares. Luego
$$\gcd(A_n,B_n)=1.$$
Si \(n\) es par, entonces \(n-1\) y \(n+1\) son impares, con lo que
$$A_n\equiv B_n\equiv 2 \pmod{8}.$$
Cada factor contiene exactamente una potencia de \(2\), y por tanto
$$\gcd(A_n,B_n)=2.$$
Cuando \(n\) es impar, \(A_n\) y \(B_n\) son coprimos. Como \(\sigma^*\) es multiplicativa sobre argumentos coprimos,
$$\sigma^*(n^4+4)=\sigma^*(A_n)\sigma^*(B_n)=Q(n-1)Q(n+1).$$
Cuando \(n\) es par, escribimos
$$A_n=2u,\qquad B_n=2v,$$
con \(u\) y \(v\) impares y coprimos. Entonces
$$Q(n-1)=\sigma^*(2u)=3\sigma^*(u),$$
$$Q(n+1)=\sigma^*(2v)=3\sigma^*(v).$$
Ademas,
$$n^4+4=A_nB_n=4uv,$$
y como \(4\), \(u\) y \(v\) son coprimos dos a dos, se obtiene
$$\sigma^*(n^4+4)=\sigma^*(4)\sigma^*(u)\sigma^*(v)=5\sigma^*(u)\sigma^*(v).$$
Al comparar ambas expresiones aparece la correccion constante
$$\sigma^*(n^4+4)=\frac{5}{9}Q(n-1)Q(n+1)\qquad(n\text{ par}).$$
La formula cerrada final es
$$\boxed{\sigma^*(n^4+4)= \begin{cases} Q(n-1)Q(n+1), & n\text{ impar},\\[4pt] \dfrac{5}{9}Q(n-1)Q(n+1), & n\text{ par}. \end{cases}}$$
Para que un primo impar \(p\) divida a \(m^2+1\), es necesario que
$$m^2\equiv -1 \pmod p.$$
Es decir, \(-1\) debe ser un residuo cuadratico modulo \(p\), lo cual solo sucede cuando
$$p\equiv 1 \pmod 4.$$
El primo \(2\) es el caso especial: \(2\mid m^2+1\) exactamente cuando \(m\) es impar, y entonces su exponente es exactamente \(1\).
Eso produce un cribado por congruencias cuadraticas:
Para \(p=2\), se actualizan todos los \(m\) impares.
Para cada primo impar \(p\equiv 1\pmod 4\), se encuentra una raiz \(r\) de \(x^2\equiv -1\pmod p\). Entonces los unicos indices posibles son las dos clases
$$m\equiv r \pmod p,\qquad m\equiv -r \pmod p.$$
En cada uno de esos indices se divide repetidamente \(m^2+1\) por \(p\) hasta obtener la potencia exacta \(p^e\parallel (m^2+1)\), y se multiplica el valor acumulado de \(Q(m)\) por \(1+p^e\).
Una vez procesados todos los primos relevantes hasta \(N+1\), cualquier factor restante mayor que \(1\) debe ser primo. En efecto, dos primos no tratados, ambos mayores que \(N+1\), tendrian producto mayor que \((N+1)^2+1\), mientras que siempre se cumple \(m^2+1\le (N+1)^2+1\). Ese residuo final aporta un ultimo factor \(1+\text{resto}\).
Para \(n=2\), tenemos
$$n^4+4=20,\qquad A_2=2,\qquad B_2=10.$$
Por tanto,
$$Q(1)=\sigma^*(2)=3,\qquad Q(3)=\sigma^*(10)=(1+2)(1+5)=18.$$
Como \(n\) es par,
$$\sigma^*(20)=\frac{5}{9}\cdot 3\cdot 18=30,$$
y entonces
$$R(20)=30-20=10.$$
Para \(n=3\), los factores son coprimos:
$$n^4+4=85,\qquad A_3=5,\qquad B_3=17.$$
Luego
$$\sigma^*(85)=Q(2)Q(4)=\sigma^*(5)\sigma^*(17)=6\cdot 18=108,$$
asi que
$$R(85)=108-85=23.$$
Las implementaciones en C++, Python y Java reservan arreglos para el residuo aun no factorizado de \(m^2+1\) y para el valor acumulado de \(Q(m)\) modulo \(10^9+7\), para todos los \(m\) entre \(0\) y \(N+1\). Incluir \(m=0\) permite tratar el termino \(n=1\) sin un caso especial, porque \(0^2+1=1\) y por tanto \(Q(0)=1\).
Despues construyen una tabla de primos hasta \(N+1\). El primo \(2\) se maneja recorriendo los indices impares. Para cada primo impar \(p\equiv 1\pmod 4\), la implementacion calcula una raiz cuadrada de \(-1\) modulo \(p\) mediante Tonelli-Shanks y recorre las dos progresiones aritmeticas correspondientes.
Cada vez que un indice es alcanzado, se elimina toda la potencia \(p\)-adica del residuo actual y se multiplica el producto unitario en curso por \(1+p^e\). Al final se incorpora un posible factor primo restante. Despues, para cada \(n\), se combinan los valores precalculados en \(n-1\) y \(n+1\), se aplica la correccion \(5/9\) cuando \(n\) es par, se resta \(n^4+4\) modulo \(10^9+7\) y se acumula la respuesta.
La criba de primos y los arreglos sobre \(0,\dots,N+1\) consumen \(O(N)\) memoria. Los barridos por clases residuales visitan aproximadamente \(2N/p\) indices para cada primo \(p\equiv 1\pmod 4\), de modo que el coste total es practicamente
$$\sum_{p\le N+1,\ p\equiv 1\!\!\!\pmod 4}\frac{N}{p}=O(N\log\log N).$$
El trabajo adicional por visita es constante, salvo extraer una potencia prima completa. En conjunto, el metodo corre en tiempo cercano a \(O(N\log\log N)\) y usa \(O(N)\) memoria.
对每个模数 \(m \gt 1\)，考虑线性映射
$$f(x)\equiv ax+b \pmod{m},\qquad 0 \lt a \lt m,\quad 0\le b \lt m.$$
如果它在所有剩余类上都是幂等的，那么它就是一个回缩：
$$f(f(x))\equiv f(x)\pmod{m}\qquad\text{对所有 }x.$$
记这类映射的个数为 \(R(m)\)。Problem 446 要求计算
$$F(N)=\sum_{n=1}^{N}R(n^4+4),$$
并给出校验值 \(F(1024)=77532377300600\)。真正的任务是在不逐个分解 \(n^4+4\) 的前提下，求出 \(F(10^7)\bmod(10^9+7)\)。
把映射再复合一次：
$$f(f(x))\equiv a(ax+b)+b\equiv a^2x+ab+b \pmod{m}.$$
要使它对每个 \(x\) 都等于 \(ax+b\)，那么 \(x\) 的系数和常数修正项都必须在模 \(m\) 下消失，因此
$$m\mid a(a-1),\qquad m\mid ab.$$
把 \(m\) 写成
$$m=\prod_{i=1}^{r}p_i^{e_i}.$$
由于 \(\gcd(a,a-1)=1\)，每个素数幂 \(p_i^{e_i}\) 必须完整地落在 \(a\) 或 \(a-1\) 其中之一上。因此，对每个 \(p_i^{e_i}\parallel m\)，都有
$$a\equiv 0 \pmod{p_i^{e_i}}\qquad\text{或}\qquad a\equiv 1 \pmod{p_i^{e_i}}.$$
这些独立选择与 \(m\) 的单位因子一一对应。若定义
$$d=\gcd(a,m),$$
则 \(d\mid m\) 且 \(\gcd(d,m/d)=1\)。反过来，每个满足 \(d \lt m\) 的单位因子都唯一决定一个合法的 \(a\) 同余类。
固定这样一个 \(a\)，再写成
$$a=d\,a_1,\qquad m=d\,m_1,\qquad \gcd(a_1,m_1)=1.$$
那么条件 \(m\mid ab\) 变成
$$d\,m_1\mid d\,a_1b \iff m_1\mid a_1b \iff m_1\mid b,$$
因为 \(a_1\) 在模 \(m_1\) 下可逆。在 \(0\le b\lt m=d\,m_1\) 中，恰好有 \(d\) 个数是 \(m_1\) 的倍数，所以每个合法的 \(a\) 恰好对应 \(d\) 个合法的 \(b\)。
于是对所有单位因子求和得到
$$R(m)=\sum_{\substack{d\parallel m\\ d \lt m}} d=\left(\sum_{d\parallel m}d\right)-m.$$
因此
$$\boxed{R(m)=\sigma^*(m)-m},$$
其中 \(\sigma^*(m)\) 表示单位因子和。若 \(m=\prod p^e\)，则
$$\sigma^*(m)=\prod_{p^e\parallel m}(1+p^e).$$
关键代数恒等式是 Sophie Germain 分解：
$$n^4+4=(n^2-2n+2)(n^2+2n+2).$$
记
$$A_n=(n-1)^2+1,\qquad B_n=(n+1)^2+1,$$
于是
$$n^4+4=A_nB_n.$$
再定义
$$Q(m)=\sigma^*(m^2+1).$$
这样 \(A_n\) 与 \(B_n\) 分别就是 \(m=n-1\) 和 \(m=n+1\) 时的 \(m^2+1\)。因此问题变成了批量预处理 \(0\le m\le N+1\) 的 \(Q(m)\)。
若 \(g\) 同时整除 \(A_n\) 与 \(B_n\)，那么它必然整除差值
$$g\mid (B_n-A_n)=4n.$$
另一方面，
$$A_n\equiv B_n\equiv 2 \pmod{n}.$$
如果某个奇素数 \(p\) 同时整除 \(A_n\) 和 \(B_n\)，由 \(p\mid 4n\) 可知 \(p\mid n\)，但这又意味着 \(A_n\equiv 2\pmod p\)，矛盾。所以公共因子只能是 \(2\) 的幂。
当 \(n\) 为奇数时，\(n-1\) 和 \(n+1\) 都是偶数，所以 \(A_n\) 和 \(B_n\) 都是奇数，从而
$$\gcd(A_n,B_n)=1.$$
当 \(n\) 为偶数时，\(n-1\) 和 \(n+1\) 都是奇数，因此
$$A_n\equiv B_n\equiv 2 \pmod{8}.$$
这说明两个因子各自恰好含有一个因子 \(2\)，于是
$$\gcd(A_n,B_n)=2.$$
若 \(n\) 为奇数，则 \(A_n\) 与 \(B_n\) 互素，而 \(\sigma^*\) 在互素情况下是乘法函数，所以
$$\sigma^*(n^4+4)=\sigma^*(A_n)\sigma^*(B_n)=Q(n-1)Q(n+1).$$
若 \(n\) 为偶数，则写成
$$A_n=2u,\qquad B_n=2v,$$
其中 \(u\)、\(v\) 都是奇数且互素。于是
$$Q(n-1)=\sigma^*(2u)=3\sigma^*(u),$$
$$Q(n+1)=\sigma^*(2v)=3\sigma^*(v).$$
另一方面，
$$n^4+4=A_nB_n=4uv,$$
而 \(4\)、\(u\)、\(v\) 两两互素，因此
$$\sigma^*(n^4+4)=\sigma^*(4)\sigma^*(u)\sigma^*(v)=5\sigma^*(u)\sigma^*(v).$$
比较两边就得到固定修正系数
$$\sigma^*(n^4+4)=\frac{5}{9}Q(n-1)Q(n+1)\qquad(n\text{ 为偶数}).$$
最终闭式为
$$\boxed{\sigma^*(n^4+4)= \begin{cases} Q(n-1)Q(n+1), & n\text{ 为奇数},\\[4pt] \dfrac{5}{9}Q(n-1)Q(n+1), & n\text{ 为偶数}. \end{cases}}$$
若奇素数 \(p\) 整除 \(m^2+1\)，那么必须有
$$m^2\equiv -1 \pmod p.$$
也就是说，\(-1\) 在模 \(p\) 下必须是二次剩余，而这只会发生在
$$p\equiv 1 \pmod 4$$
时。素数 \(2\) 是特殊情况：\(2\mid m^2+1\) 当且仅当 \(m\) 为奇数，而且此时 \(2\) 的指数恰好等于 \(1\)。
因此可以做一个基于二次同余的筛法：
对 \(p=2\)，处理所有奇数 \(m\)。
对每个满足 \(p\equiv 1\pmod 4\) 的奇素数，先求出方程 \(x^2\equiv -1\pmod p\) 的一个根 \(r\)。那么可能的下标只会落在两条同余类上：
$$m\equiv r \pmod p,\qquad m\equiv -r \pmod p.$$
对这些下标，把 \(m^2+1\) 中的 \(p\) 反复除尽，得到准确的幂次 \(p^e\parallel (m^2+1)\)，再把运行中的 \(Q(m)\) 乘上 \(1+p^e\)。
当所有不超过 \(N+1\) 的相关素数都处理完以后，若还有大于 \(1\) 的剩余因子，它只能是一个素数。因为如果还剩两个都大于 \(N+1\) 的素数，它们的乘积会超过 \((N+1)^2+1\)，但始终有 \(m^2+1\le (N+1)^2+1\)。于是最后再乘一个 \(1+\text{剩余因子}\) 即可完成 \(Q(m)\)。
当 \(n=2\) 时，
$$n^4+4=20,\qquad A_2=2,\qquad B_2=10.$$
因此
$$Q(1)=\sigma^*(2)=3,\qquad Q(3)=\sigma^*(10)=(1+2)(1+5)=18.$$
由于 \(n\) 是偶数，
$$\sigma^*(20)=\frac{5}{9}\cdot 3\cdot 18=30,$$
从而
$$R(20)=30-20=10.$$
当 \(n=3\) 时，两个因子互素：
$$n^4+4=85,\qquad A_3=5,\qquad B_3=17.$$
于是
$$\sigma^*(85)=Q(2)Q(4)=\sigma^*(5)\sigma^*(17)=6\cdot 18=108,$$
所以
$$R(85)=108-85=23.$$
C++、Python 和 Java 实现都会为每个 \(0\le m\le N+1\) 维护两个数组：一个保存 \(m^2+1\) 尚未分解的剩余部分，另一个保存 \(Q(m)\) 在模 \(10^9+7\) 下的当前值。把 \(m=0\) 也放进去，可以让第一项 \(n=1\) 直接统一处理，因为 \(0^2+1=1\)，所以 \(Q(0)=1\)。
接着实现会建立到 \(N+1\) 为止的素数表。素数 \(2\) 通过扫描所有奇数下标来处理。对于每个满足 \(p\equiv 1\pmod 4\) 的奇素数，程序使用 Tonelli-Shanks 算法求出 \(-1\) 在模 \(p\) 下的平方根，然后沿着两条等差序列扫描所有可能下标。
每当命中某个下标时，实现就把当前剩余值中的完整 \(p\)-进幂次全部剥离出来，并把单位因子积乘上 \(1+p^e\)。筛法结束后，再补上可能剩余的那个大素数因子。最后对每个 \(n\)，组合 \(n-1\) 与 \(n+1\) 位置的预处理结果，若 \(n\) 为偶数则乘上 \(5/9\) 修正，再减去 \(n^4+4\) 的模值并累加到答案中。
素数预处理和长度为 \(N+2\) 的数组都需要 \(O(N)\) 空间。对每个 \(p\equiv 1\pmod 4\) 的素数，按剩余类扫描大约访问 \(2N/p\) 个下标，因此总工作量在实践中接近
$$\sum_{p\le N+1,\ p\equiv 1\!\!\!\pmod 4}\frac{N}{p}=O(N\log\log N).$$
每次访问除去剥离一个完整素数幂之外，只需要常数级算术操作，所以整体复杂度接近 \(O(N\log\log N)\) 时间和 \(O(N)\) 空间。
Для каждого модуля \(m \gt 1\) рассматриваются линейные отображения
$$f(x)\equiv ax+b \pmod{m},\qquad 0 \lt a \lt m,\quad 0\le b \lt m.$$
Отображение является ретракцией, если оно идемпотентно на всех классах вычетов:
$$f(f(x))\equiv f(x)\pmod{m}\qquad\text{для всех }x.$$
Пусть \(R(m)\) обозначает число таких отображений. В задаче 446 требуется вычислить
$$F(N)=\sum_{n=1}^{N}R(n^4+4),$$
причем дан контроль \(F(1024)=77532377300600\). Нужно найти \(F(10^7)\bmod(10^9+7)\), не раскладывая каждое число \(n^4+4\) отдельно.
Составим отображение само с собой:
$$f(f(x))\equiv a(ax+b)+b\equiv a^2x+ab+b \pmod{m}.$$
Чтобы это совпадало с \(ax+b\) для любого \(x\), коэффициент при \(x\) и постоянная поправка должны обращаться в нуль по модулю \(m\). Значит,
$$m\mid a(a-1),\qquad m\mid ab.$$
Пусть
$$m=\prod_{i=1}^{r}p_i^{e_i}.$$
Так как \(\gcd(a,a-1)=1\), каждая простая степень \(p_i^{e_i}\) должна целиком делить ровно один из множителей \(a\) или \(a-1\). Поэтому для каждого \(p_i^{e_i}\parallel m\) имеем
$$a\equiv 0 \pmod{p_i^{e_i}}\qquad\text{или}\qquad a\equiv 1 \pmod{p_i^{e_i}}.$$
Эти независимые выборы естественно соответствуют унитарным делителям числа \(m\). Если положить
$$d=\gcd(a,m),$$
то выполняются условия \(d\mid m\) и \(\gcd(d,m/d)=1\). Обратно, каждый унитарный делитель \(d \lt m\) задает ровно один допустимый класс для \(a\).
Зафиксируем такой \(a\) и запишем
$$a=d\,a_1,\qquad m=d\,m_1,\qquad \gcd(a_1,m_1)=1.$$
Тогда условие \(m\mid ab\) эквивалентно
$$d\,m_1\mid d\,a_1b \iff m_1\mid a_1b \iff m_1\mid b,$$
поскольку \(a_1\) обратим по модулю \(m_1\). Среди остатков \(0\le b\lt m=d\,m_1\) ровно \(d\) чисел кратны \(m_1\). Следовательно, каждому допустимому \(a\) соответствуют ровно \(d\) значений \(b\).
Суммируя по всем унитарным делителям, получаем
$$R(m)=\sum_{\substack{d\parallel m\\ d \lt m}} d=\left(\sum_{d\parallel m}d\right)-m.$$
Итак,
$$\boxed{R(m)=\sigma^*(m)-m},$$
где \(\sigma^*(m)\) - сумма унитарных делителей. Если \(m=\prod p^e\), то
$$\sigma^*(m)=\prod_{p^e\parallel m}(1+p^e).$$
Ключевая алгебраическая формула - тождество Софи Жермен:
$$n^4+4=(n^2-2n+2)(n^2+2n+2).$$
Обозначим
$$A_n=(n-1)^2+1,\qquad B_n=(n+1)^2+1,$$
тогда
$$n^4+4=A_nB_n.$$
Также введем
$$Q(m)=\sigma^*(m^2+1).$$
Числа \(A_n\) и \(B_n\) - это просто значения \(m^2+1\) при \(m=n-1\) и \(m=n+1\). Значит, задача сводится к совместному вычислению всех \(Q(m)\) для \(0\le m\le N+1\).
Любой общий делитель \(g\) чисел \(A_n\) и \(B_n\) обязан делить их разность:
$$g\mid (B_n-A_n)=4n.$$
Кроме того,
$$A_n\equiv B_n\equiv 2 \pmod{n}.$$
Если бы некоторый нечетный простой \(p\) делил оба числа, то из \(p\mid 4n\) следовало бы \(p\mid n\), но тогда \(A_n\equiv 2\pmod p\), что невозможно. Значит, общий делитель может быть только степенью двойки.
Если \(n\) нечетно, то \(n-1\) и \(n+1\) четны, следовательно, \(A_n\) и \(B_n\) нечетны. Тогда
$$\gcd(A_n,B_n)=1.$$
Если \(n\) четно, то \(n-1\) и \(n+1\) нечетны, и потому
$$A_n\equiv B_n\equiv 2 \pmod{8}.$$
Каждый множитель содержит ровно одну степень двойки, а значит
$$\gcd(A_n,B_n)=2.$$
Если \(n\) нечетно, то \(A_n\) и \(B_n\) взаимно просты. Поскольку \(\sigma^*\) мультипликативна на взаимно простых аргументах, имеем
$$\sigma^*(n^4+4)=\sigma^*(A_n)\sigma^*(B_n)=Q(n-1)Q(n+1).$$
Если \(n\) четно, запишем
$$A_n=2u,\qquad B_n=2v,$$
где \(u\) и \(v\) нечетны и взаимно просты. Тогда
$$Q(n-1)=\sigma^*(2u)=3\sigma^*(u),$$
$$Q(n+1)=\sigma^*(2v)=3\sigma^*(v).$$
С другой стороны,
$$n^4+4=A_nB_n=4uv,$$
а числа \(4\), \(u\), \(v\) попарно взаимно просты, поэтому
$$\sigma^*(n^4+4)=\sigma^*(4)\sigma^*(u)\sigma^*(v)=5\sigma^*(u)\sigma^*(v).$$
Сравнение двух выражений дает постоянную поправку
$$\sigma^*(n^4+4)=\frac{5}{9}Q(n-1)Q(n+1)\qquad(n\text{ четно}).$$
Итоговая формула такова:
$$\boxed{\sigma^*(n^4+4)= \begin{cases} Q(n-1)Q(n+1), & n\text{ нечетно},\\[4pt] \dfrac{5}{9}Q(n-1)Q(n+1), & n\text{ четно}. \end{cases}}$$
Чтобы нечетный простой \(p\) делил \(m^2+1\), необходимо
$$m^2\equiv -1 \pmod p.$$
То есть \(-1\) должно быть квадратичным вычетом по модулю \(p\), а это возможно только при
$$p\equiv 1 \pmod 4.$$
Простой \(2\) - отдельный случай: \(2\mid m^2+1\) тогда и только тогда, когда \(m\) нечетно, и показатель двойки при этом равен ровно \(1\).
Отсюда возникает решето по квадратным сравнениям:
Для \(p=2\) обновляются все нечетные \(m\).
Для каждого простого \(p\equiv 1\pmod 4\) сначала находится один корень \(r\) сравнения \(x^2\equiv -1\pmod p\). После этого возможны только две арифметические прогрессии индексов:
$$m\equiv r \pmod p,\qquad m\equiv -r \pmod p.$$
Для каждого такого \(m\) число \(m^2+1\) делится на \(p\) до тех пор, пока не будет выделена точная степень \(p^e\parallel (m^2+1)\), после чего текущее значение \(Q(m)\) умножается на \(1+p^e\).
После обработки всех нужных простых до \(N+1\) любой остаточный множитель больше \(1\) обязан быть простым. Действительно, два необработанных простых, оба большие \(N+1\), имели бы произведение больше \((N+1)^2+1\), тогда как всегда \(m^2+1\le (N+1)^2+1\). Этот остаток и дает последний множитель \(1+\text{остаток}\).
Для \(n=2\) имеем
$$n^4+4=20,\qquad A_2=2,\qquad B_2=10.$$
Следовательно,
$$Q(1)=\sigma^*(2)=3,\qquad Q(3)=\sigma^*(10)=(1+2)(1+5)=18.$$
Так как \(n\) четно,
$$\sigma^*(20)=\frac{5}{9}\cdot 3\cdot 18=30,$$
и значит
$$R(20)=30-20=10.$$
Для \(n=3\) множители взаимно просты:
$$n^4+4=85,\qquad A_3=5,\qquad B_3=17.$$
Поэтому
$$\sigma^*(85)=Q(2)Q(4)=\sigma^*(5)\sigma^*(17)=6\cdot 18=108,$$
откуда
$$R(85)=108-85=23.$$
Реализации на C++, Python и Java выделяют массивы для еще неразложенного остатка числа \(m^2+1\) и для текущего значения \(Q(m)\) по модулю \(10^9+7\), для всех \(0\le m\le N+1\). Включение \(m=0\) позволяет обработать первый член \(n=1\) без отдельной ветки, так как \(0^2+1=1\) и \(Q(0)=1\).
Затем строится таблица простых чисел до \(N+1\). Простой \(2\) обрабатывается проходом по нечетным индексам. Для каждого нечетного простого \(p\equiv 1\pmod 4\) программа с помощью алгоритма Тонелли-Шенкса находит квадратный корень из \(-1\) по модулю \(p\), после чего проходит две соответствующие арифметические прогрессии индексов.
При попадании в индекс реализация вынимает из текущего остатка полную \(p\)-адическую степень и умножает текущий унитарный множитель на \(1+p^e\). После завершения решета добавляется возможный оставшийся простой множитель. Наконец, для каждого \(n\) берутся заранее вычисленные значения в точках \(n-1\) и \(n+1\), при четном \(n\) применяется поправка \(5/9\), затем вычитается \(n^4+4\) по модулю \(10^9+7\), и все члены суммируются.
Предварительное построение таблицы простых и массивы длины \(N+2\) требуют \(O(N)\) памяти. Проходы по классам вычетов посещают примерно \(2N/p\) индексов для каждого простого \(p\equiv 1\pmod 4\), поэтому суммарная трудоемкость на практике близка к
$$\sum_{p\le N+1,\ p\equiv 1\!\!\!\pmod 4}\frac{N}{p}=O(N\log\log N).$$
Дополнительная работа на одно посещение постоянна, если не считать удаления полной простой степени. Итак, итоговая сложность близка к \(O(N\log\log N)\) по времени и \(O(N)\) по памяти.
لكل عدد معياري \(m \gt 1\)، ننظر إلى الدوال الخطية
$$f(x)\equiv ax+b \pmod{m},\qquad 0 \lt a \lt m,\quad 0\le b \lt m.$$
تكون الدالة ارتدادا إذا كانت idempotent على جميع فئات البواقي:
$$f(f(x))\equiv f(x)\pmod{m}.$$
ولنرمز بعدد هذه الدوال بـ \(R(m)\). في المسألة 446 نريد حساب
$$F(N)=\sum_{n=1}^{N}R(n^4+4),$$
ومعطى كقيمة تحقق أن \(F(1024)=77532377300600\). المطلوب هو الوصول إلى \(F(10^7)\bmod(10^9+7)\) من دون تحليل كل عدد من الشكل \(n^4+4\) على حدة.
إذا ركبنا الدالة مع نفسها مرة أخرى نحصل على
$$f(f(x))\equiv a(ax+b)+b\equiv a^2x+ab+b \pmod{m}.$$
ولكي يساوي هذا المقدار \(ax+b\) لكل \(x\)، يجب أن يختفي كل من معامل \(x\) والجزء الثابت modulo \(m\). لذلك يلزم
$$m\mid a(a-1),\qquad m\mid ab.$$
اكتب
$$m=\prod_{i=1}^{r}p_i^{e_i}.$$
بما أن \(\gcd(a,a-1)=1\)، فإن كل قوة أولية \(p_i^{e_i}\) يجب أن تقع كاملة في أحد العاملين \(a\) أو \(a-1\). إذن لكل \(p_i^{e_i}\parallel m\) لدينا
$$a\equiv 0 \pmod{p_i^{e_i}}\qquad\text{or}\qquad a\equiv 1 \pmod{p_i^{e_i}}.$$
هذه الاختيارات المستقلة تطابق القواسم الوحدوية للعدد \(m\). فإذا عرفنا
$$d=\gcd(a,m),$$
فإن \(d\mid m\) و \(\gcd(d,m/d)=1\). وبالعكس، كل قاسم وحدوي \(d \lt m\) يحدد فئة وحيدة مسموحة لـ \(a\).
والآن ثبّت مثل هذا \(a\)، واكتب
$$a=d\,a_1,\qquad m=d\,m_1,\qquad \gcd(a_1,m_1)=1.$$
عندها يصبح الشرط \(m\mid ab\) مكافئا لـ
$$d\,m_1\mid d\,a_1b \iff m_1\mid a_1b \iff m_1\mid b,$$
لأن \(a_1\) قابل للعكس modulo \(m_1\). ومن بين البواقي \(0\le b\lt m=d\,m_1\) يوجد بالضبط \(d\) مضاعفات للعدد \(m_1\). لذلك كل قيمة مسموحة لـ \(a\) تعطي بالضبط \(d\) قيما ممكنة لـ \(b\).
وبالجمع على جميع القواسم الوحدوية نحصل على
$$R(m)=\sum_{\substack{d\parallel m\\ d \lt m}} d=\left(\sum_{d\parallel m}d\right)-m.$$
إذن
$$\boxed{R(m)=\sigma^*(m)-m},$$
حيث \(\sigma^*(m)\) هو مجموع القواسم الوحدوية. وإذا كان \(m=\prod p^e\)، فإن
$$\sigma^*(m)=\prod_{p^e\parallel m}(1+p^e).$$
الهوية الجبرية الاساسية هنا هي هوية Sophie Germain:
$$n^4+4=(n^2-2n+2)(n^2+2n+2).$$
لنكتب
$$A_n=(n-1)^2+1,\qquad B_n=(n+1)^2+1,$$
وعندئذ
$$n^4+4=A_nB_n.$$
كما نعرف
$$Q(m)=\sigma^*(m^2+1).$$
وبذلك يصبح \(A_n\) و \(B_n\) هما بالضبط القيمتان \(m^2+1\) عند \(m=n-1\) و \(m=n+1\). لذا تتحول المسألة إلى حساب جميع قيم \(Q(m)\) دفعة واحدة من أجل \(0\le m\le N+1\).
أي قاسم مشترك \(g\) لـ \(A_n\) و \(B_n\) يجب أن يقسم الفرق بينهما:
$$g\mid (B_n-A_n)=4n.$$
ومن جهة أخرى
$$A_n\equiv B_n\equiv 2 \pmod{n}.$$
إذا كان هناك عدد أولي فردي \(p\) يقسم العاملين معا، فمن \(p\mid 4n\) ينتج \(p\mid n\)، لكن هذا يجعل \(A_n\equiv 2\pmod p\)، وهذا مستحيل. إذن القاسم المشترك لا يمكن أن يكون إلا قوة للعدد \(2\).
إذا كان \(n\) فرديا، فإن \(n-1\) و \(n+1\) زوجيان، وبالتالي يكون \(A_n\) و \(B_n\) فرديين، فنحصل على
$$\gcd(A_n,B_n)=1.$$
أما إذا كان \(n\) زوجيا، فإن \(n-1\) و \(n+1\) فرديان، ولذلك
$$A_n\equiv B_n\equiv 2 \pmod{8}.$$
وهذا يعني أن كلا العاملين يحتوي على عامل \(2\) واحد فقط، ومن ثم
$$\gcd(A_n,B_n)=2.$$
عندما يكون \(n\) فرديا، يكون \(A_n\) و \(B_n\) متباينين اوليا. وبما أن \(\sigma^*\) دالة ضربية على المدخلات المتباينة اوليا، فإن
$$\sigma^*(n^4+4)=\sigma^*(A_n)\sigma^*(B_n)=Q(n-1)Q(n+1).$$
وعندما يكون \(n\) زوجيا نكتب
$$A_n=2u,\qquad B_n=2v,$$
حيث \(u\) و \(v\) فرديان ومتباينان اوليا. عندها
$$Q(n-1)=\sigma^*(2u)=3\sigma^*(u),$$
$$Q(n+1)=\sigma^*(2v)=3\sigma^*(v).$$
كذلك لدينا
$$n^4+4=A_nB_n=4uv,$$
ومادام \(4\) و \(u\) و \(v\) متباينة اوليا اثنين اثنين، نحصل على
$$\sigma^*(n^4+4)=\sigma^*(4)\sigma^*(u)\sigma^*(v)=5\sigma^*(u)\sigma^*(v).$$
بمقارنة العبارتين يظهر عامل التصحيح الثابت
$$\sigma^*(n^4+4)=\frac{5}{9}Q(n-1)Q(n+1).$$
إذن نحصل على الصيغة النهائية التالية:
إذا كان \(n\) فرديا، فإن
$$\sigma^*(n^4+4)=Q(n-1)Q(n+1).$$
وإذا كان \(n\) زوجيا، فإن
$$\sigma^*(n^4+4)=\frac{5}{9}Q(n-1)Q(n+1).$$
لكي يقسم عدد أولي فردي \(p\) التعبير \(m^2+1\)، لا بد أن يتحقق
$$m^2\equiv -1 \pmod p.$$
أي إن \(-1\) يجب أن يكون بقايا تربيعية modulo \(p\)، وهذا لا يحدث إلا إذا
$$p\equiv 1 \pmod 4.$$
أما العدد الأولي \(2\) فهو الحالة الخاصة: \(2\mid m^2+1\) بالضبط عندما يكون \(m\) فرديا، وعندها يكون اس \(2\) مساويا تماما لـ \(1\).
ومن هنا نحصل على غربال مبني على المتطابقات التربيعية:
بالنسبة إلى \(p=2\)، نعالج جميع قيم \(m\) الفردية.
وبالنسبة إلى كل عدد أولي فردي يحقق \(p\equiv 1\pmod 4\)، نحسب جذرا واحدا \(r\) للمعادلة \(x^2\equiv -1\pmod p\). عندئذ تكون الفهارس الممكنة فقط ضمن فئتي البواقي
$$m\equiv r \pmod p,\qquad m\equiv -r \pmod p.$$
وعند كل فهرس من هذه الفهارس نقسم \(m^2+1\) على \(p\) مرات متتالية حتى نستخرج القوة الدقيقة \(p^e\parallel (m^2+1)\)، ثم نضرب القيمة الجارية لـ \(Q(m)\) في \(1+p^e\).
وبعد معالجة جميع الاعداد الاولية الملائمة حتى \(N+1\)، فإن أي عامل متبق أكبر من \(1\) لا بد أن يكون هو نفسه عددا اوليا. ذلك أن وجود عاملين اوليين متبقين، وكلاهما أكبر من \(N+1\)، سيجعل حاصل ضربهما أكبر من \((N+1)^2+1\)، بينما لدينا دائما \(m^2+1\le (N+1)^2+1\). وإذا رمزنا لهذا العامل المتبقي بـ \(\ell\)، فإن الاضافة الاخيرة تكون هي العامل \(1+\ell\).
عند \(n=2\) نجد
$$n^4+4=20,\qquad A_2=2,\qquad B_2=10.$$
ومن ثم
$$Q(1)=\sigma^*(2)=3,\qquad Q(3)=\sigma^*(10)=(1+2)(1+5)=18.$$
وبما أن \(n\) زوجي، فإن
$$\sigma^*(20)=\frac{5}{9}\cdot 3\cdot 18=30,$$
ولذلك
$$R(20)=30-20=10.$$
وعند \(n=3\) يكون العاملان متباينين اوليا:
$$n^4+4=85,\qquad A_3=5,\qquad B_3=17.$$
إذن
$$\sigma^*(85)=Q(2)Q(4)=\sigma^*(5)\sigma^*(17)=6\cdot 18=108,$$
ومن ثم
$$R(85)=108-85=23.$$
تقوم تطبيقات C++ وPython وJava بإنشاء مصفوفتين لكل \(0\le m\le N+1\): واحدة للاحتفاظ بالجزء غير المفكك بعد من \(m^2+1\)، وأخرى للاحتفاظ بالقيمة الجارية لـ \(Q(m)\) modulo \(10^9+7\). وإدراج \(m=0\) يسمح بالتعامل مع الحد الاول \(n=1\) من دون حالة خاصة، لأن \(0^2+1=1\) وبالتالي \(Q(0)=1\).
بعد ذلك تبني التنفيذات جدولا للاعداد الاولية حتى \(N+1\). ويجري التعامل مع \(2\) عبر المرور على جميع الفهارس الفردية. ولكل عدد أولي فردي يحقق \(p\equiv 1\pmod 4\)، تستخدم الشيفرة خوارزمية Tonelli-Shanks لايجاد جذر تربيعي لـ \(-1\) modulo \(p\)، ثم تمشي على التقدّمين الحسابيين الموافقين لهاتين الفئتين من البواقي.
وعند كل فهرس يمر به الغربال، تزيل الشيفرة القوة \(p\)-adic الكاملة من الباقي الحالي، ثم تضرب حاصل القواسم الوحدوية الجاري في \(1+p^e\). وبعد انتهاء الغربلة يضاف العامل الاولي المتبقي - إن وجد - مرة اخيرة. وفي الحلقة النهائية، تجمع الشيفرة القيمتين المحسوبتين مسبقا عند \(n-1\) و\(n+1\)، وتطبق عامل \(5/9\) إذا كان \(n\) زوجيا، ثم تطرح \(n^4+4\) modulo \(10^9+7\) وتضيف النتيجة إلى المجموع النهائي.
تحتاج مرحلة توليد الاعداد الاولية والمصفوفات على المجال \(0,\dots,N+1\) إلى ذاكرة \(O(N)\). أما مسوح فئات البواقي فتزور تقريبا \(2N/p\) فهرسا لكل عدد أولي يحقق \(p\equiv 1\pmod 4\)، ولذلك تكون الكلفة الكلية عمليا قريبة من
$$\sum_{p\le N+1,\ p\equiv 1\!\!\!\pmod 4}\frac{N}{p}=O(N\log\log N).$$
والعمل الاضافي في كل زيارة ثابت، باستثناء نزع قوة أولية كاملة. لذلك تعمل الطريقة في زمن قريب من \(O(N\log\log N)\) وتستخدم ذاكرة \(O(N)\).