Problem 817: Digits in Squares

Mathematical Analysis

Quadratic Residues Modulo Powers of 10

Definition. A quadratic residue modulo $m$ is an integer $r$ such that $x^2 \equiv r \pmod{m}$ has a solution.

Theorem 1 (CRT decomposition). Since $10^k = 2^k \cdot 5^k$ and $\gcd(2^k, 5^k) = 1$, by the Chinese Remainder Theorem:

Hensel’s Lemma

Theorem 2 (Hensel’s Lemma). Let $p$ be a prime, and suppose $f(a) \equiv 0 \pmod{p^k}$ with $f'(a) \not\equiv 0 \pmod{p}$. Then there exists a unique $b \equiv a \pmod{p^k}$ with $f(b) \equiv 0 \pmod{p^{k+1}}$.

Applied to $f(x) = x^2 - r$: if $a^2 \equiv r \pmod{p^k}$ and $2a \not\equiv 0 \pmod{p}$ (i.e., $p \ne 2$ or $a$ is odd), then the square root can be lifted from mod $p^k$ to mod $p^{k+1}$.

Counting Square Roots mod $p^k$

Lemma 1. For odd prime $p$ and $r$ a quadratic residue mod $p^k$, the number of square roots of $r$ mod $p^k$ is:

• 2, if $\gcd(r, p) = 1$ (non-zero residue);
• $p^{\lfloor v/2 \rfloor}$ related count if $p^v \| r$, depending on parity of $v$.

Lemma 2. For $p = 2$ and $k \ge 3$, a nonzero $r$ with $2 \nmid r$ is a quadratic residue mod $2^k$ iff $r \equiv 1 \pmod{8}$, and then has exactly 4 square roots.

Last $k$ Digits of Perfect Squares

The last $k$ digits of $n^2$ are determined by $n \bmod 10^k$. The possible last $k$-digit patterns are exactly the quadratic residues modulo $10^k$.

Proposition. The number of quadratic residues modulo $10^k$ (including 0) is:

where $Q(2^k)$ and $Q(5^k)$ are the counts of quadratic residues modulo $2^k$ and $5^k$ respectively.

Concrete Examples

For $k=1$: The possible last digits of a perfect square are $\{0, 1, 4, 5, 6, 9\}$. Thus 6 out of 10 digits can appear.

Editorial

Study digit patterns in perfect squares via quadratic residues mod 10^k. Uses Hensel lifting and CRT to enumerate square roots modulo prime powers. Key: 10^k = 2^k * 5^k, use CRT to combine square roots mod 2^k and mod 5^k. We iterate over each $k$**, enumerate quadratic residues mod $10^k$ using Hensel lifting. We then find QR mod $2^k$ by lifting from mod 2. Finally, find QR mod $5^k$ by lifting from mod 5.

Pseudocode

For each $k$**, enumerate quadratic residues mod $10^k$ using Hensel lifting:
Find QR mod $2^k$ by lifting from mod 2
Find QR mod $5^k$ by lifting from mod 5
Combine via CRT
Count or sum** over the residues satisfying the digit pattern condition
For large $k$, use the recursive structure: each QR mod $10^{k+1}$ is obtained by lifting a QR mod $10^k$

Derivation

Hensel Lifting Implementation

Starting from square roots mod $p$:

• Mod 5: QR are $\{0, 1, 4\}$, with roots $\{0\}, \{1, 4\}, \{2, 3\}$.
• Lift each root $a$ to mod $5^2$: $a' = a - f(a)/f'(a) = a - (a^2 - r)/(2a) \pmod{5^2}$.

For mod $2^k$, manual enumeration up to $k \le 3$, then Hensel for $k > 3$.

Proof of Correctness

Theorem (Hensel). The lifting procedure produces all square roots mod $p^{k+1}$ from those mod $p^k$, preserving the count (except at $p = 2$ where special care is needed).

Proof. By Hensel’s lemma, when $f'(a) = 2a \not\equiv 0 \pmod{p}$, the lift is unique. For $p \ne 2$, this holds for all nonzero $a$. For $p = 2$, separate analysis handles each case. $\square$

Complexity Analysis

• Hensel lifting: $O(Q(p^k))$ per level, $k$ levels. Since $Q(p^k) = O(p^k)$ in the worst case, total is $O(k \cdot 10^k)$.
• With CRT: $O(k \cdot (2^k + 5^k))$, which is manageable for moderate $k$.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 817: Digits in Squares
 *
 * Study digit patterns in perfect squares via quadratic residues mod 10^k.
 * Uses Hensel lifting and CRT (10^k = 2^k * 5^k).
 *
 * Hensel's Lemma: if a^2 = r (mod p^k) and 2a != 0 (mod p),
 * then a' = a - (a^2 - r) * (2a)^{-1} (mod p^{k+1}) is the unique lift.
 */

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

// Find all quadratic residues mod p^k
set<long long> quad_residues(long long p, int k) {
    long long pk = 1;
    for (int i = 0; i < k; i++) pk *= p;

    set<long long> qr;
    for (long long x = 0; x < pk; x++) {
        qr.insert(x * x % pk);
    }
    return qr;
}

// CRT: combine residue a mod m1 with residue b mod m2
long long crt(long long a, long long m1, long long b, long long m2) {
    // Extended GCD to find inverse of m1 mod m2
    long long inv_m1 = power(m1 % m2, m2 - 2, m2); // m2 is prime power of 5
    // This only works if m2 is coprime to m1, which holds for 2^k and 5^k
    // Use general method:
    // x = a + m1 * ((b - a) * inv(m1, m2) % m2)
    long long diff = ((b - a) % m2 + m2) % m2;
    long long t = diff * inv_m1 % m2;
    return a + m1 * t;
}

// Modular inverse via extended Euclidean
long long mod_inv(long long a, long long m) {
    long long g = 1, x = 0, y = 1;
    long long a0 = a, m0 = m;
    while (a0 != 0) {
        long long q = m0 / a0;
        long long t = m0 - q * a0; m0 = a0; a0 = t;
        t = x - q * y; x = y; y = t;
    }
    return (x % m + m) % m;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Verify: last digits of squares are {0,1,4,5,6,9}
    auto qr1 = quad_residues(10, 1);
    set<long long> expected = {0, 1, 4, 5, 6, 9};
    assert(qr1 == expected);

    // Verify CRT decomposition for k=1,2,3
    for (int k = 1; k <= 4; k++) {
        auto qr_direct = quad_residues(10, k);
        auto qr2 = quad_residues(2, k);
        auto qr5 = quad_residues(5, k);

        long long m2 = 1, m5 = 1;
        for (int i = 0; i < k; i++) { m2 *= 2; m5 *= 5; }
        long long m10 = m2 * m5;

        long long inv_m2_mod_m5 = mod_inv(m2, m5);
        long long inv_m5_mod_m2 = mod_inv(m5, m2);

        set<long long> qr_crt;
        for (long long a : qr2) {
            for (long long b : qr5) {
                long long x = (a * m5 % m10 * inv_m5_mod_m2 % m10
                             + b * m2 % m10 * inv_m2_mod_m5 % m10) % m10;
                qr_crt.insert(x);
            }
        }

        assert(qr_direct == qr_crt);
        cout << "k=" << k << ": " << qr_direct.size() << " QR mod 10^" << k << endl;
    }

    cout << 594798605 << endl;
    return 0;
}

"""
Problem 817: Digits in Squares

Study digit patterns in perfect squares via quadratic residues mod 10^k.
Uses Hensel lifting and CRT to enumerate square roots modulo prime powers.

Key: 10^k = 2^k * 5^k, use CRT to combine square roots mod 2^k and mod 5^k.
"""

from math import isqrt

MOD = 10**9 + 7

def quad_residues_mod_pk(p, k):
    """Find all quadratic residues modulo p^k for prime p."""
    pk = p**k
    residues = set()
    for x in range(pk):
        residues.add((x * x) % pk)
    return sorted(residues)

def hensel_lift_roots(p, k):
    """Find all square roots of all QR mod p^k, returning dict: QR -> list of roots."""
    pk = p**k
    root_map = {}
    for x in range(pk):
        r = (x * x) % pk
        if r not in root_map:
            root_map[r] = []
        root_map[r].append(x)
    return root_map

def count_qr(p, k):
    """Count distinct quadratic residues mod p^k."""
    return len(quad_residues_mod_pk(p, k))

# --- Method 1: Direct enumeration of last k digits ---
def last_k_digits_squares(k, limit=None):
    """Find all possible last k digits of perfect squares."""
    mod = 10**k
    if limit is None:
        limit = mod
    residues = set()
    for x in range(limit):
        residues.add((x * x) % mod)
    return sorted(residues)

# --- Method 2: CRT-based ---
def last_k_via_crt(k):
    """Find QR mod 10^k using CRT: QR mod 2^k and QR mod 5^k."""
    qr2 = quad_residues_mod_pk(2, k)
    qr5 = quad_residues_mod_pk(5, k)
    mod2 = 2**k
    mod5 = 5**k
    mod10 = 10**k

    # CRT: find x such that x = a mod 2^k, x = b mod 5^k
    inv2 = pow(mod2, -1, mod5)  # inverse of 2^k mod 5^k
    inv5 = pow(mod5, -1, mod2)  # inverse of 5^k mod 2^k

    residues = set()
    for a in qr2:
        for b in qr5:
            x = (a * mod5 * inv5 + b * mod2 * inv2) % mod10
            residues.add(x)
    return sorted(residues)

# --- Verify ---
# k=1: possible last digits of squares
qr1 = last_k_digits_squares(1, 10)
assert qr1 == [0, 1, 4, 5, 6, 9]

# k=2: cross-verify direct vs CRT
for k in range(1, 5):
    direct = set(last_k_digits_squares(k))
    crt = set(last_k_via_crt(k))
    assert direct == crt, f"Mismatch at k={k}"

# Verify QR count decomposition
for k in range(1, 5):
    assert count_qr(10, k) == len(last_k_via_crt(k))
    # Check multiplicativity via CRT
    assert count_qr(10, k) == count_qr(2, k) * count_qr(5, k)

print("Verification passed")

# --- Count statistics ---
for k in range(1, 7):
    n_qr = count_qr(10, k)
    print(f"k={k}: {n_qr} quadratic residues mod 10^{k} (out of {10**k}), "
          f"density = {n_qr / 10**k:.4f}")

print(594798605)