Codeforces 55D Beautiful Numbers：數位 DP + LCM 狀態壓縮求區間美麗數個數

Codeforces 55D Beautiful Numbers：數位 DP + LCM 狀態壓縮求區間美麗數個數

「美麗數」定義：能被其所有非零數位整除的正整數。給定 [L, R] (≤ 9×10¹⁸)，多組查詢統計區間內美麗數個數。經典數位 DP + LCM 狀態壓縮 + 模 2520 技巧。

核心數學洞察

數字能被所有非零數位整除 ⇔ 能被這些數位的 LCM 整除。
1~9 的 LCM = 2520。
設數字為 X，任意數位子集的 LCM 必是 2520 的約數。2520 的約數僅 48 個（實際 50 個含 0）。

狀態設計

• pos：數位位置
• mod：X % 2520（0~2519），利用同餘性質：X % lcm == 0 ⇔ (X % 2520) % lcm == 0
• lcm_idx：當前非零數位集合的 LCM 在約數列表中的索引（0~49）
• tight：是否受上界約束

DP 狀態數：20 × 2520 × 50 ≈ 252 萬，記憶化搜索可行。

狀態轉移

ll dfs(int pos, int mod, int lcm_idx, bool tight) {
    if (pos == -1) return (mod % lcm_val[lcm_idx] == 0);
    if (!tight && dp[pos][mod][lcm_idx] != -1) return dp[pos][mod][lcm_idx];
    int up = tight ? digit[pos] : 9;
    ll ans = 0;
    for (int d = 0; d <= up; d++) {
        int nmod = (mod * 10 + d) % 2520;
        int nlcm = d ? lcm(lcm_val[lcm_idx], d) : lcm_val[lcm_idx];
        int nidx = lcm_to_idx[nlcm];
        ans += dfs(pos-1, nmod, nidx, tight && d==up);
    }
    if (!tight) dp[pos][mod][lcm_idx] = ans;
    return ans;
}

關鍵預處理