NeFut Logo NeFut
中 Admin Login

Deep Integration of Digit DP and Algebraic Number Theory: Dynamic Programming Analysis of Divisibility Problems

Published at: 2026-05-29 00:44 Last updated: 2026-06-06 13:04
#C++ #Tutorial

Core Logic and Mathematical Principles

Standard digit DP (Section 18.1) typically deals with counting problems that are highly dependent on decimal literal features such as "the specific shape of numbers, adjacent differences, and whether specific substrings are included." However, the frequently examined direction in the NOIP improvement group and provincial selections often merges digit DP with algebraic number theory (divisibility, congruence systems, and greatest common divisors).

When introducing the constraint of "divisibility" (for example, determining whether a number can be divided by the sum of its digits or a fixed number $M$), we cannot perform modulus checks after the number is fully assembled, as this would degrade into brute force enumeration. We must utilize the topological additivity and multiplicativity of congruences to maintain the divisibility state in real-time as we progress through the digits.

1. Dynamic Transmission of Digit State Machines in Congruence Systems

Let the value represented by the prefix digits filled from high to low be $X$. Now we are preparing to fill in a digit $d$ (where $0 \le d \le 9$) at the current position. According to the algebraic principles of positional notation, the new prefix value $X'$ will become:

$$X' = X \cdot 10 + d$$

If we are concerned about the divisibility of this number by a large prime $M$, since modular arithmetic satisfies:

$$(X \cdot 10 + d) \bmod M = \left( (X \bmod M) \cdot 10 + d \right) \bmod M$$

This means that we do not need to record the macro value of $X$ in the state, but only need to record the remainder state of $X \bmod M$. This algebraic dimensional reduction successfully collapses the infinite integer space into a finite congruence state machine of size only $M$.

2. Collapse of Dynamic Modulus Systems through Least Common Multiple (LCM)

Taking the classic problem "Hate Nineteen" (finding numbers in a range that can be divided by the sum of their digits) as an example.

$$X \equiv R \pmod G \implies X \equiv R \pmod m \quad (\forall m \le 162)$$

Thus, we only need to maintain the remainder of the number $X$ against the global least common multiple $G$ during the search process. However, in practice, the LCM of $1 \sim 162$ is an enormous astronomical number. In fact, we can dynamically maintain the LCM of the digit sums that have already appeared, or directly include both the "current remainder" and the "current sum of digits" into the state dimensions, utilizing memoization for extremely sparse grid pruning.

State Design and Algorithm Derivation

Taking the classic number theory digit DP problem as an example: "How many numbers in the interval $[L, R]$ can be divided by the product of their non-zero digits?"

1. Definition of State Space

Since the least common multiple of all digits from $1$ to $9$ is $\text{lcm}(1, 2, 3, 4, 5, 6, 7, 8, 9) = 2520$. The prime factors of any non-zero digit product can only include $2, 3, 5, 7$, so the final product must be divisible by $2520$. We can uniformly take modulus $MOD = 2520$ during the search.

The DFS state space is designed as: int dfs(int pos, int sum_mod, int current_lcm, bool lead, bool limit)

2. State Transition Equations and Congruence Advancement

When enumerating the digit $i$ at the current position:

C++ Standard Source Code (NOIP/Provincial Selection High-Difficulty Number Theory Template)

The following code is an efficient implementation for "divisibility of digit products." To prevent the f array from experiencing memory overflow (MLE) due to the third dimension current_lcm reaching 2520, the code introduces a discretization mapping operator. Since the combination LCM of $1 \sim 9$ actually has only 48 possible values, the 2520 dimensions are mapped to 48 dimensions, reducing constants and space by a factor of 50.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int BASE_MOD = 2520;

int digits[20];
int f[20][BASE_MOD][50]; // Optimization: third dimension uses discretized LCM indices (48 total)
int lcm_map[BASE_MOD + 5]; // Mapping table from actual LCM to discretized indices

// Algebraic operator: compute greatest common divisor
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// Algebraic operator: compute least common multiple
int lcm(int a, int b) {
    if (a == 0 || b == 0) return a + b;
    return (a * b) / gcd(a, b);
}

// Preprocessing: discretize all factors of 2520 to simplify state space
void preprocess() {
    int id = 0;
    for (int i = 1; i <= BASE_MOD; ++i) {
        if (BASE_MOD % i == 0) {
            lcm_map[i] = id++;
        }
    }
}

// pos: digit; sum_mod: remainder when uniformly taken modulo 2520; curr_lcm: current non-zero digit's LCM
int dfs(int pos, int sum_mod, int curr_lcm, bool lead, bool limit) {
    if (pos < 0) {
        // Endgame number theory check: Can the global remainder be divided by the LCM of the effective digits?
        return sum_mod % curr_lcm == 0 ? 1 : 0;
    }

    // Only when unrestricted and not leading zero can we use the reused factor index
    int lcm_id = lcm_map[curr_lcm];
    if (!limit && !lead && f[pos][sum_mod][lcm_id] != -1) {
        return f[pos][sum_mod][lcm_id];
    }

    int up = limit ? digits[pos] : 9;
    int res = 0;

    for (int i = 0; i <= up; ++i) {
        int next_mod = (sum_mod * 10 + i) % BASE_MOD;
        int next_lcm = (lead && i == 0) ? curr_lcm : lcm(curr_lcm, i);

        res += dfs(pos - 1, next_mod, next_lcm, lead && (i == 0), limit && (i == up));
    }

    if (!limit && !lead) {
        f[pos][sum_mod][lcm_id] = res;
    }
    return res;
}

long long solve(long long n) {
    if (n <= 0) return 0;
    int len = 0;
    while (n > 0) {
        digits[len++] = n % 10;
        n /= 10;
    }
    // Initialize LCM to 1 (multiplicative identity)
    return dfs(len - 1, 0, 1, true, true);
}

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

    preprocess();
    memset(f, -1, sizeof(f)); // Global lifetime reuse cache

    long long l, r;
    if (cin >> l >> r) {
        cout << solve(r) - solve(l - 1) << "\n";
    }

    return 0;
}

NOIP Practical Pitfall Guide

1. Dynamic Modulus Not Safely Initialized (Zero Modulus Causes Crash)

2. Ignoring Modulus Propagation Leading to Topological State Misalignment

Classic NOIP/Luogu Problems

1. Luogu P4127 [AHOI2009] Similar Distribution

2. Luogu P2657 [SCOI2009] Windy Numbers

Original Source: local://18.2
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS