special

Algoritmul, pas cu pas

Ce numere sunt speciale?

Un număr special are două cifre ($10..99$) cu pătrat de trei cifre, deci numărul e în $10..31$. Verificând fiecare:

• $11 \to 121$: cifra zecilor $2 = 1 + 1$ ✓;
• $22 \to 484$: cifra zecilor $8 = 4 + 4$ ✓;

și niciun altul. Deci numerele speciale sunt $\{11, 22\}$.

Cerința 1 — numărarea lui 11 și 22

Matricea are până la $10^{12}$ elemente — nu o construim. Pentru fiecare valoare țintă $t \in \{11, 22\}$ și fiecare linie $i$, numărăm coloanele $j \in [0, M)$ cu $(15i + 4j + 2025) \equiv t \pmod K \iff 4j \equiv r \pmod K, \quad r = (t - 2025 - 15i) \bmod K$ Aceasta e o congruență liniară: are soluții doar dacă $\gcd(4, K) \mid r$; soluțiile sunt $j \equiv j_0 \pmod{K/\gcd(4,K)}$, iar numărul lor în $[0, M)$ se află prin împărțire. Total $O(N)$.

Cerința 2 — întâlniri aproape speciale

Ioana ajunge la $(i, j)$ la timpul $i \cdot M + j$ (parcurgere pe linii); Mihai la $j \cdot N + i$ (pe coloane). Se întâlnesc când timpurile coincid: $i \cdot M + j = j \cdot N + i \iff i (M - 1) = j (N - 1)$ Enumerăm aceste celule: cu $g = \gcd(M-1, N-1)$, ele sunt $i = \frac{N-1}{g} \cdot k$, $j = \frac{M-1}{g} \cdot k$ pentru $k = 0, 1, \dots$ (cât timp $i < N$, $j < M$).

Un număr e aproape special dacă are cel puțin $3$ cifre (ca să putem elimina cel puțin una și să rămână $11$ sau $22$) și conține de cel puțin două ori cifra $1$ sau cifra $2$.