Let \(S(m,n)\) be the minimum number of moves needed to move the red counter from the top-left corner of an \(m\times n\) board to the bottom-right corner, with the empty cell initially at the bottom-right corner.
The problem asks for the number of grids such that
$$S(m,n)=p^2,\qquad p<10^6,\ p\text{ prime}.$$
The key fact is that the sliding game has an affine move formula, so the problem becomes a pure lattice-point count for each prime square.
1) Symmetry and small data.
Because rotating the board swaps \(m\) and \(n\) without changing the puzzle,
$$S(m,n)=S(n,m).$$
A brute-force BFS on small boards gives
$$S(2,2)=5,\quad S(3,2)=9,\quad S(4,2)=15,\quad S(5,2)=21,$$
$$S(4,3)=17,\quad S(5,4)=25,\quad S(6,5)=33.$$
The pattern is clear:
$$S(m,2)=6m-9\qquad (m\ge 3),$$
and every extra row beyond \(2\) adds exactly two more moves.
2) Closed form for non-square boards.
Assume \(m>n\ge 2\). Starting from the \(m\times 2\) strip, each extra row gives two extra blank-cell shuffles, so
$$S(m,n)=S(m,2)+2(n-2)=6m+2n-13.$$
This formula matches the sample from the statement:
$$S(5,4)=6\cdot 5+2\cdot 4-13=25.$$
3) What about square boards?
For \(m=n\ge 3\), brute force gives
$$S(3,3)=13,\quad S(4,4)=21,\quad S(5,5)=29,$$
so the square case follows
$$S(n,n)=8n-11.$$
But for an odd prime \(p\),
$$p^2\equiv 1\pmod 8,$$
whereas
$$8n-11\equiv 5\pmod 8.$$
So no square board can satisfy \(S(n,n)=p^2\). The case \(p=2\) also fails. Therefore only the non-square formula matters for prime squares.
4) Convert the move equation into an integer interval.
Set
$$q=p^2.$$
We must count integer pairs \((m,n)\) with \(m>n\ge2\) such that
$$6m+2n-13=q.$$
Divide by \(2\):
$$3m+n=\frac{q+13}{2}=:h.$$
Now solve for \(n\):
$$n=h-3m.$$
The conditions become:
From \(n\ge 2\),
$$m\le \left\lfloor\frac{h-2}{3}\right\rfloor.$$
From \(m>n\),
$$m>h-3m\iff 4m>h\iff m\ge \left\lfloor\frac{h}{4}\right\rfloor+1.$$
So the valid values of \(m\) lie in the interval
$$m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
5) Why the final count is multiplied by \(2\).
The interval above counts only boards with \(m>n\). But each such board has a transposed partner \(n\times m\), and both are distinct grids in the problem statement. Therefore the contribution of \(q=p^2\) is
$$f(q)=2\cdot \max\bigl(0,\ m_{\max}-m_{\min}+1\bigr).$$
This is exactly the formula implemented in the C++ solver.
6) Simplify the formula for odd primes \(p>3\).
Every odd prime larger than \(3\) satisfies
$$p^2\equiv 1\pmod{24},$$
so write
$$p^2=24k+1.$$
Then
$$h=\frac{p^2+13}{2}=12k+7,$$
and therefore
$$m_{\min}=\left\lfloor\frac{12k+7}{4}\right\rfloor+1=3k+2,$$
$$m_{\max}=\left\lfloor\frac{12k+5}{3}\right\rfloor=4k+1.$$
The number of admissible \(m\) values is
$$m_{\max}-m_{\min}+1=(4k+1)-(3k+2)+1=k,$$
so
$$f(p^2)=2k=\frac{p^2-1}{12}\qquad (p>3).$$
The exceptional prime \(p=3\) gives
$$q=9,\quad h=11,\quad m_{\min}=3,\quad m_{\max}=3,\quad f(9)=2.$$
And \(p=2\) contributes \(0\).
7) Final counting formula.
Hence
$$\#\{(m,n):S(m,n)=p^2,\ p<P\} = 2+\sum_{\substack{3<p<P\\ p\text{ prime}}}\frac{p^2-1}{12},$$
with the leading \(2\) coming from \(p=3\).
The sample \(p<10\). The primes are \(2,3,5,7\).
\(p=2\) contributes \(0\), \(p=3\) contributes \(2\), \(p=5\) contributes \(2\), and \(p=7\) contributes \(4\). So the total is
$$0+2+2+4=8,$$
which matches the checkpoint in the code.
The sample \(p<100\). Summing the same formula over all primes below \(100\) gives
$$5482,$$
exactly as stated in the problem.
1) Generate all primes \(p<10^6\) with the sieve of Eratosthenes.
2) For each prime, compute \(q=p^2\).
3) Evaluate
$$h=\frac{q+13}{2},\qquad m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
4) Add
$$2\cdot \max(0,m_{\max}-m_{\min}+1).$$
This is \(O(1)\) work per prime.
The sieve costs \(O(P\log\log P)\) time and \(O(P)\) memory. After that, the summation is linear in the number of primes, with constant-time arithmetic for each one.
The implementation verifies
$$\text{solve}(10)=8,\qquad \text{solve}(100)=5482.$$
The full answer is
$$2057774861813004.$$
Sei \(S(m,n)\) die minimale Zugzahl des Schiebespiels auf einem \(m\times n\)-Brett. Gesucht ist die Anzahl der Gitter mit
$$S(m,n)=p^2,\qquad p<10^6,\ p\text{ prim}.$$
Der springende Punkt ist, dass \(S(m,n)\) fuer alle relevanten Bretter eine affine Formel besitzt. Danach bleibt nur noch eine diophantische Zaehlung pro Primquadrat.
1) Symmetrie und kleine Werte. Offenbar gilt
$$S(m,n)=S(n,m).$$
Eine BFS fuer kleine Bretter liefert
$$S(2,2)=5,\quad S(3,2)=9,\quad S(4,2)=15,\quad S(5,2)=21,$$
$$S(4,3)=17,\quad S(5,4)=25,\quad S(6,5)=33.$$
Daraus liest man ab:
$$S(m,2)=6m-9\qquad (m\ge3),$$
und jede weitere Zeile erhoeht die Minimalzahl um genau \(2\).
2) Geschlossene Form fuer nichtquadratische Bretter.
Fuer \(m>n\ge2\) folgt daher
$$S(m,n)=6m+2n-13.$$
Das Beispiel der Aufgabenstellung ergibt sofort
$$S(5,4)=6\cdot5+2\cdot4-13=25.$$
3) Quadratische Bretter tragen nie zu Primquadraten bei.
Fuer \(m=n\ge3\) zeigen kleine Werte
$$S(n,n)=8n-11.$$
Fuer ungerade Primzahlen gilt aber \(p^2\equiv1\pmod8\), waehrend
$$8n-11\equiv5\pmod8.$$
Also kann kein Quadratbrett \(S(n,n)=p^2\) erfuellen. \(p=2\) funktioniert ebenfalls nicht.
4) Umformung in ein Intervall.
Setze
$$q=p^2.$$
Gesucht sind \(m>n\ge2\) mit
$$6m+2n-13=q.$$
Mit
$$h=\frac{q+13}{2}$$
wird das zu
$$3m+n=h,\qquad n=h-3m.$$
Die Nebenbedingungen liefern
$$m\le \left\lfloor\frac{h-2}{3}\right\rfloor,\qquad m\ge \left\lfloor\frac{h}{4}\right\rfloor+1.$$
Also
$$m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
5) Warum der Faktor \(2\) erscheint.
Das Intervall zaehlt nur \(m>n\). Jedes solcher Bretter besitzt das transponierte Brett \(n\times m\) mit demselben Wert. Darum ist der Beitrag von \(q=p^2\)
$$f(q)=2\cdot\max\bigl(0,m_{\max}-m_{\min}+1\bigr).$$
6) Vereinfachung fuer \(p>3\).
Fuer jede Primzahl \(p>3\) gilt
$$p^2=24k+1.$$
Dann ist
$$h=12k+7,\qquad m_{\min}=3k+2,\qquad m_{\max}=4k+1,$$
also
$$f(p^2)=2k=\frac{p^2-1}{12}.$$
Der Sonderfall \(p=3\) liefert \(f(9)=2\), und \(p=2\) liefert \(0\).
Fuer \(p<10\) sind die Primzahlen \(2,3,5,7\). Die Beitraege sind \(0,2,2,4\), also insgesamt
$$8.$$
Fuer \(p<100\) ergibt dieselbe Summation
$$5482.$$
1) Erzeuge alle Primzahlen \(p<10^6\) mit dem Sieb des Eratosthenes.
2) Berechne \(q=p^2\).
3) Bestimme
$$h=\frac{q+13}{2},\qquad m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
4) Addiere
$$2\cdot\max(0,m_{\max}-m_{\min}+1).$$
Das Sieb kostet \(O(P\log\log P)\) Zeit und \(O(P)\) Speicher. Danach ist konstante Arbeit pro Primzahl noetig.
Die Implementierung prueft
$$\text{solve}(10)=8,\qquad \text{solve}(100)=5482,$$
und liefert schliesslich
$$2057774861813004.$$
\(S(m,n)\), \(m\times n\) tahtasinda kirmizi tasi sol ustten sag alta tasimak icin gereken minimum hamle sayisi olsun. Saymamiz gereken sey
$$S(m,n)=p^2,\qquad p<10^6,\ p\text{ asal}$$
kosulunu saglayan tahtalarin sayisidir.
Kilit nokta su: oyun minimumu, ilgili butun tahtalarda dogrusal bir formule iniyor. Ondan sonra is asal kare basi basit bir tam sayi aralik sayimina donusuyor.
1) Simetri ve kucuk tablo.
Tahtayi dondurmek \(m\) ile \(n\)'yi degistirir ama oyunu degistirmez:
$$S(m,n)=S(n,m).$$
Kucuk boyutlarda brute-force BFS su degerleri verir:
$$S(2,2)=5,\quad S(3,2)=9,\quad S(4,2)=15,\quad S(5,2)=21,$$
$$S(4,3)=17,\quad S(5,4)=25,\quad S(6,5)=33.$$
Buradan iki desen gorulur:
$$S(m,2)=6m-9\qquad (m\ge3),$$
ve \(2\)'den sonraki her ek satir tam \(2\) hamle ekler.
2) Kare olmayan tahtalar icin kapali form.
\(m>n\ge2\) icin dolayisiyla
$$S(m,n)=6m+2n-13.$$
Problemdeki ornek hemen dogrulanir:
$$S(5,4)=6\cdot5+2\cdot4-13=25.$$
3) Kare tahtalar neden hic katkı vermiyor?
\(m=n\ge3\) icin brute-force degerleri
$$S(3,3)=13,\quad S(4,4)=21,\quad S(5,5)=29$$
verdiginden kare durumda
$$S(n,n)=8n-11$$
olur. Oysa tek asal \(p\) icin
$$p^2\equiv1\pmod8,$$
ama
$$8n-11\equiv5\pmod8.$$
Bu nedenle hicbir kare tahta \(p^2\)'ye esit olamaz. \(p=2\) de zaten calismaz. Demek ki prime-square sayiminda sadece \(m>n\) durumu onemlidir.
4) Denklem aralik sayimina donusuyor.
$$q=p^2$$
yazalim. O zaman saymamiz gerekenler
$$6m+2n-13=q$$
denklemini saglayan \(m>n\ge2\) ciftleridir. Su tanimi yapalim:
$$h=\frac{q+13}{2}.$$
Boylece denklem
$$3m+n=h,\qquad n=h-3m$$
olur. Kosullardan
$$n\ge2\ \Longrightarrow\ m\le\left\lfloor\frac{h-2}{3}\right\rfloor,$$
$$m>n\ \Longrightarrow\ 4m>h\ \Longrightarrow\ m\ge\left\lfloor\frac{h}{4}\right\rfloor+1$$
elde edilir. Dolayisiyla
$$m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
5) Neden sonda \(2\) ile carpiyoruz?
Bu aralik yalnizca \(m>n\) tahtalarini sayar. Fakat her boyle tahta icin ayrica \(n\times m\) transpozesi de vardir ve problem bunlari ayri grid olarak sayar. Bu yuzden \(q=p^2\) icin katkı
$$f(q)=2\cdot \max\bigl(0,\ m_{\max}-m_{\min}+1\bigr)$$
olur. Kodun kullandigi formül tam olarak budur.
6) \(p>3\) icin sadeleşme.
\(3\)'ten buyuk her asal icin
$$p^2\equiv1\pmod{24}$$
oldugundan
$$p^2=24k+1$$
yazabiliriz. O zaman
$$h=12k+7,$$
$$m_{\min}=3k+2,\qquad m_{\max}=4k+1.$$
Dolayisiyla uygun \(m\) sayisi \(k\), toplam katkı ise
$$f(p^2)=2k=\frac{p^2-1}{12}$$
olur. Ozel durumlar:
$$f(9)=2,\qquad f(4)=0.$$
7) Son toplam.
Boylece
$$2+\sum_{\substack{3<p<P\\ p\text{ asal}}}\frac{p^2-1}{12}$$
formulune ulasiriz; bastaki \(2\) terimi \(p=3\)'ten gelir.
\(p<10\) ornegi. Asallar \(2,3,5,7\)'dir. Katkilar sirasiyla \(0,2,2,4\) olur. Toplam:
$$8.$$
\(p<100\) ornegi. Ayni toplama bu kez \(100\)'den kucuk tum asallar icin uygulaninca
$$5482$$
elde edilir; bu da problemde verilen checkpoint'tir.
1) Eratosthenes eleği ile \(10^6\)'dan kucuk tum asallari uret.
2) Her asal icin \(q=p^2\) hesapla.
3) Su degerleri bul:
$$h=\frac{q+13}{2},\qquad m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
4) Katki olarak
$$2\cdot\max(0,m_{\max}-m_{\min}+1)$$
ekle.
Elek \(O(P\log\log P)\) zaman ve \(O(P)\) bellek kullanir. Sonraki toplama asallar uzerinde dogrusaldir ve her asal icin sabit zamanli aritmetik yapar.
Kod su degerleri dogrular:
$$\text{solve}(10)=8,\qquad \text{solve}(100)=5482.$$
Tam cevap ise
$$2057774861813004$$
olarak cikar.
Sea \(S(m,n)\) el numero minimo de movimientos del juego deslizante sobre una tabla \(m\times n\). Debemos contar las tablas para las que
$$S(m,n)=p^2,\qquad p<10^6,\ p\text{ primo}.$$
La idea clave es que \(S(m,n)\) se vuelve una formula afín, y entonces el problema se reduce a contar soluciones enteras para cada cuadrado primo.
1) Simetria y tabla pequeña.
Se tiene
$$S(m,n)=S(n,m).$$
Una BFS sobre tableros pequeños da
$$S(2,2)=5,\quad S(3,2)=9,\quad S(4,2)=15,\quad S(5,2)=21,$$
$$S(4,3)=17,\quad S(5,4)=25,\quad S(6,5)=33.$$
Se observa que
$$S(m,2)=6m-9\qquad (m\ge3),$$
y cada fila extra por encima de \(2\) agrega exactamente \(2\) movimientos.
2) Formula cerrada para tableros no cuadrados.
Para \(m>n\ge2\), por tanto,
$$S(m,n)=6m+2n-13.$$
Esto verifica el ejemplo oficial:
$$S(5,4)=6\cdot5+2\cdot4-13=25.$$
3) Los tableros cuadrados no cuentan para \(p^2\).
En el caso \(m=n\ge3\), los datos pequeños siguen
$$S(n,n)=8n-11.$$
Pero para un primo impar \(p\),
$$p^2\equiv1\pmod8,$$
mientras que
$$8n-11\equiv5\pmod8.$$
Asi que ningun tablero cuadrado puede satisfacer \(S(n,n)=p^2\). El caso \(p=2\) tampoco funciona.
4) La ecuacion de movimientos se vuelve un intervalo entero.
Sea
$$q=p^2.$$
Hay que contar \((m,n)\) con \(m>n\ge2\) tales que
$$6m+2n-13=q.$$
Definimos
$$h=\frac{q+13}{2},$$
de modo que
$$3m+n=h,\qquad n=h-3m.$$
Las restricciones dan
$$m\le\left\lfloor\frac{h-2}{3}\right\rfloor,\qquad m\ge\left\lfloor\frac{h}{4}\right\rfloor+1.$$
Asi,
$$m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
5) Por que aparece el factor \(2\).
Ese intervalo solo cuenta \(m>n\). Pero el tablero transpuesto \(n\times m\) tambien es una solucion distinta del problema. Por tanto, la contribucion de \(q=p^2\) es
$$f(q)=2\cdot \max\bigl(0,m_{\max}-m_{\min}+1\bigr).$$
6) Simplificacion para \(p>3\).
Todo primo \(p>3\) satisface
$$p^2=24k+1.$$
Entonces
$$h=12k+7,\qquad m_{\min}=3k+2,\qquad m_{\max}=4k+1,$$
y el numero total de tableros es
$$f(p^2)=2k=\frac{p^2-1}{12}.$$
El caso especial \(p=3\) da \(f(9)=2\), mientras que \(p=2\) aporta \(0\).
Para \(p<10\), las contribuciones de \(2,3,5,7\) son \(0,2,2,4\), y por tanto el total es
$$8.$$
Para \(p<100\), la misma suma produce
$$5482.$$
1) Generar todos los primos menores que \(10^6\) con la criba de Eratostenes.
2) Para cada primo, calcular \(q=p^2\).
3) Evaluar
$$h=\frac{q+13}{2},\qquad m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
4) Sumar
$$2\cdot\max(0,m_{\max}-m_{\min}+1).$$
La criba cuesta \(O(P\log\log P)\) tiempo y \(O(P)\) memoria. Despues, cada primo requiere solo aritmetica de tiempo constante.
La implementacion verifica
$$\text{solve}(10)=8,\qquad \text{solve}(100)=5482,$$
y devuelve finalmente
$$2057774861813004.$$
设 \(S(m,n)\) 为在 \(m\times n\) 棋盘上完成滑动游戏所需的最少步数。题目要求统计满足
$$S(m,n)=p^2,\qquad p<10^6,\ p\text{为素数}$$
的棋盘个数。
关键事实是：对所有相关棋盘，\(S(m,n)\) 会化成一个仿射公式，问题于是变成对每个素数平方做整数区间计数。
1) 对称性与小规模数据。
显然有
$$S(m,n)=S(n,m).$$
小规模 BFS 得到
$$S(2,2)=5,\quad S(3,2)=9,\quad S(4,2)=15,\quad S(5,2)=21,$$
$$S(4,3)=17,\quad S(5,4)=25,\quad S(6,5)=33.$$
从中可以看出
$$S(m,2)=6m-9\qquad (m\ge3),$$
而每多一行，最优步数只再增加 \(2\)。
2) 非方形棋盘的闭式。
因此对 \(m>n\ge2\)，有
$$S(m,n)=6m+2n-13.$$
这立刻验证了题面样例：
$$S(5,4)=6\cdot5+2\cdot4-13=25.$$
3) 为什么正方形棋盘不会贡献素数平方。
当 \(m=n\ge3\) 时，小数据满足
$$S(n,n)=8n-11.$$
但奇素数 \(p\) 满足
$$p^2\equiv1\pmod8,$$
而
$$8n-11\equiv5\pmod8.$$
所以 \(S(n,n)\) 不可能等于 \(p^2\)。\(p=2\) 也不成立。于是素数平方计数只需考虑 \(m>n\)。
4) 把移动方程改写成整数区间。
令
$$q=p^2.$$
需要统计满足
$$6m+2n-13=q$$
的整数对 \(m>n\ge2\)。定义
$$h=\frac{q+13}{2},$$
则方程变成
$$3m+n=h,\qquad n=h-3m.$$
由 \(n\ge2\) 得
$$m\le\left\lfloor\frac{h-2}{3}\right\rfloor,$$
由 \(m>n\) 得
$$4m>h\iff m\ge\left\lfloor\frac{h}{4}\right\rfloor+1.$$
所以
$$m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
5) 为什么最后要乘 \(2\).
上面的区间只统计了 \(m>n\) 的情况。但每个这样的棋盘还有一个转置棋盘 \(n\times m\)，题目把它也算作不同的 grid。因此 \(q=p^2\) 的贡献为
$$f(q)=2\cdot \max\bigl(0,\ m_{\max}-m_{\min}+1\bigr).$$
6) 对 \(p>3\) 的进一步化简。
所有大于 \(3\) 的素数都满足
$$p^2=24k+1.$$
于是
$$h=12k+7,\qquad m_{\min}=3k+2,\qquad m_{\max}=4k+1,$$
从而
$$f(p^2)=2k=\frac{p^2-1}{12}.$$
特例 \(p=3\) 给出 \(f(9)=2\)，而 \(p=2\) 给出 \(0\)。
当 \(p<10\) 时，素数是 \(2,3,5,7\)，对应贡献是 \(0,2,2,4\)，总和为
$$8.$$
当 \(p<100\) 时，累加结果为
$$5482,$$
与题目给出的样例一致。
1) 用埃氏筛生成所有小于 \(10^6\) 的素数。
2) 对每个素数计算 \(q=p^2\)。
3) 计算
$$h=\frac{q+13}{2},\qquad m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
4) 累加
$$2\cdot\max(0,m_{\max}-m_{\min}+1).$$
筛法耗时 \(O(P\log\log P)\)，空间 \(O(P)\)。之后对每个素数只做常数时间运算。
程序验证了
$$\text{solve}(10)=8,\qquad \text{solve}(100)=5482,$$
最终答案是
$$2057774861813004.$$
Пусть \(S(m,n)\) - минимальное число ходов в игре на доске \(m\times n\). Нужно посчитать количество досок, для которых
$$S(m,n)=p^2,\qquad p<10^6,\ p\text{ простое}.$$
Ключевая идея: для всех важных случаев \(S(m,n)\) задается аффинной формулой. После этого остается только посчитать целочисленные решения для каждого простого квадрата.
1) Симметрия и маленькие значения.
Очевидно, что
$$S(m,n)=S(n,m).$$
Брутфорс-BFS на малых досках дает
$$S(2,2)=5,\quad S(3,2)=9,\quad S(4,2)=15,\quad S(5,2)=21,$$
$$S(4,3)=17,\quad S(5,4)=25,\quad S(6,5)=33.$$
Отсюда видно:
$$S(m,2)=6m-9\qquad (m\ge3),$$
а каждая дополнительная строка сверх \(2\) добавляет ровно \(2\) хода.
2) Формула для не квадратных досок.
Следовательно, для \(m>n\ge2\)
$$S(m,n)=6m+2n-13.$$
Пример из условия:
$$S(5,4)=6\cdot5+2\cdot4-13=25.$$
3) Квадратные доски не дают простых квадратов.
Для \(m=n\ge3\) малые значения подчиняются формуле
$$S(n,n)=8n-11.$$
Но для нечетного простого \(p\)
$$p^2\equiv1\pmod8,$$
тогда как
$$8n-11\equiv5\pmod8.$$
Значит, квадратная доска никогда не удовлетворяет \(S(n,n)=p^2\). Случай \(p=2\) тоже невозможен.
4) Преобразование уравнения в целочисленный интервал.
Положим
$$q=p^2.$$
Нужно считать пары \(m>n\ge2\), удовлетворяющие
$$6m+2n-13=q.$$
Пусть
$$h=\frac{q+13}{2}.$$
Тогда
$$3m+n=h,\qquad n=h-3m.$$
Из условий получаем
$$m\le\left\lfloor\frac{h-2}{3}\right\rfloor,\qquad m\ge\left\lfloor\frac{h}{4}\right\rfloor+1.$$
То есть
$$m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
5) Откуда берется множитель \(2\).
Этот интервал считает только доски с \(m>n\). Но каждая такая доска имеет транспонированную доску \(n\times m\), и задача считает ее отдельно. Поэтому вклад \(q=p^2\) равен
$$f(q)=2\cdot\max\bigl(0,m_{\max}-m_{\min}+1\bigr).$$
6) Упрощение для \(p>3\).
Для каждого простого \(p>3\)
$$p^2=24k+1.$$
Тогда
$$h=12k+7,\qquad m_{\min}=3k+2,\qquad m_{\max}=4k+1,$$
и потому
$$f(p^2)=2k=\frac{p^2-1}{12}.$$
Особые случаи: \(f(9)=2\) и \(f(4)=0\).
Для \(p<10\) вклад простых \(2,3,5,7\) равен \(0,2,2,4\), так что сумма равна
$$8.$$
Для \(p<100\) та же формула дает
$$5482.$$
1) Построить все простые \(p<10^6\) решетом Эратосфена.
2) Для каждого простого вычислить \(q=p^2\).
3) Найти
$$h=\frac{q+13}{2},\qquad m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
4) Прибавить
$$2\cdot\max(0,m_{\max}-m_{\min}+1).$$
Решето работает за \(O(P\log\log P)\) времени и \(O(P)\) памяти. После этого на каждый простой требуется только постоянное число арифметических операций.
Код проверяет
$$\text{solve}(10)=8,\qquad \text{solve}(100)=5482,$$
а финальный ответ равен
$$2057774861813004.$$
لتكن \(S(m,n)\) أقل عدد من الحركات اللازمة لإنهاء لعبة الانزلاق على لوحة \(m\times n\). المطلوب هو عد اللوحات التي تحقق
$$S(m,n)=p^2,\qquad p<10^6,\ p\text{ أولي}.$$
الفكرة الأساسية أن \(S(m,n)\) تتحول، في جميع الحالات المهمة هنا، إلى صيغة خطية بسيطة. بعد ذلك تصبح المسألة مجرد عد لحلول صحيحة لكل مربع أولي.
1) التماثل والبيانات الصغيرة.
لدينا
$$S(m,n)=S(n,m).$$
وبالتحقق العددي على الأحجام الصغيرة نحصل على
$$S(2,2)=5,\quad S(3,2)=9,\quad S(4,2)=15,\quad S(5,2)=21,$$
$$S(4,3)=17,\quad S(5,4)=25,\quad S(6,5)=33.$$
ومن هنا يظهر النمط
$$S(m,2)=6m-9\qquad (m\ge3),$$
وأن كل صف إضافي فوق \(2\) يزيد العدد الأدنى بمقدار \(2\) فقط.
2) الصيغة المغلقة للمستطيلات غير المربعة.
لذلك عندما \(m>n\ge2\) نحصل على
$$S(m,n)=6m+2n-13.$$
وهذا يطابق المثال المعطى:
$$S(5,4)=6\cdot5+2\cdot4-13=25.$$
3) لماذا لا تساهم المربعات أبدًا.
في الحالة \(m=n\ge3\) تعطي القيم الصغيرة
$$S(n,n)=8n-11.$$
لكن لأي أولي فردي \(p\) لدينا
$$p^2\equiv1\pmod8,$$
بينما
$$8n-11\equiv5\pmod8.$$
إذن لا يمكن لأي لوحة مربعة أن تحقق \(S(n,n)=p^2\). كما أن \(p=2\) لا يعطي حلًا أيضًا.
4) تحويل معادلة الحركات إلى مجال صحيح.
ضع
$$q=p^2.$$
نريد عد الأزواج \(m>n\ge2\) التي تحقق
$$6m+2n-13=q.$$
نعرف
$$h=\frac{q+13}{2},$$
فتصبح المعادلة
$$3m+n=h,\qquad n=h-3m.$$
ومن الشرط \(n\ge2\) نحصل على
$$m\le\left\lfloor\frac{h-2}{3}\right\rfloor,$$
ومن الشرط \(m>n\) نحصل على
$$4m>h\iff m\ge\left\lfloor\frac{h}{4}\right\rfloor+1.$$
إذًا
$$m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
5) لماذا يظهر العامل \(2\).
المجال السابق يحصي فقط الحالات \(m>n\). لكن لكل لوحة من هذا النوع توجد اللوحة المنقولة \(n\times m\)، وهي لوحة مختلفة في نص المسألة. لذلك تكون مساهمة \(q=p^2\) مساوية لـ
$$f(q)=2\cdot \max\bigl(0,\ m_{\max}-m_{\min}+1\bigr).$$
6) تبسيط خاص عندما \(p>3\).
كل أولي أكبر من \(3\) يحقق
$$p^2=24k+1.$$
وعندئذ
$$h=12k+7,\qquad m_{\min}=3k+2,\qquad m_{\max}=4k+1,$$
ومن ثم
$$f(p^2)=2k=\frac{p^2-1}{12}.$$
أما الحالة الخاصة \(p=3\) فتعطي \(f(9)=2\)، و\(p=2\) يعطي \(0\).
عندما \(p<10\)، تكون المساهمات للأعداد الأولية \(2,3,5,7\) هي \(0,2,2,4\)، ومن ثم يكون المجموع
$$8.$$
وعندما \(p<100\)، فإن الجمع نفسه يعطي
$$5482,$$
وهو بالضبط المثال المذكور في المسألة.
1) توليد جميع الأعداد الأولية الأصغر من \(10^6\) بمنخل إراتوستينس.
2) لكل أولي نحسب \(q=p^2\).
3) نحسب
$$h=\frac{q+13}{2},\qquad m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$$
4) ثم نضيف
$$2\cdot\max(0,m_{\max}-m_{\min}+1).$$
المنخل يحتاج إلى \(O(P\log\log P)\) زمنًا و\(O(P)\) ذاكرة. بعد ذلك نحتاج فقط إلى حسابات ثابتة الزمن لكل أولي.
يتحقق الكود من
$$\text{solve}(10)=8,\qquad \text{solve}(100)=5482,$$
والنتيجة النهائية هي
$$2057774861813004.$$