「PA 2020」Liczba Potyczkowa 题解

算法思路

本题使用数位动态规划（数位DP） 结合状态压缩和数学性质来统计区间 $[l, r]$ 内的 Potyczkow 数。核心思想是利用数字的整除性质和最小公倍数来减少状态空间。

关键数学观察

1. 数字集合与最小公倍数

Potyczkow 数必须能被其所有数字整除，等价于能被这些数字的最小公倍数（LCM）整除。

2. 关键常数 $2520$

• $2520 = \operatorname{lcm}(1,2,3,4,5,6,7,8,9)$
• 所有数字的 LCM 一定是 $2520$ 的约数
• 因此模 $2520$ 的余数信息足够判断整除性

代码解析

预处理阶段

const int m = 2520;
const int p[4] = {2, 3, 5, 7};  // 2520的质因数分解

int b[m + 1][10];  // b[v][d]表示数字d对v的质因数覆盖情况

void init() {
    for (int i = 1; i <= m; ++i) {
        vector<int> c(4);  // 记录i的质因数指数
        auto v = i;
        
        // 分解质因数
        for (int j = 0; j < 4; ++j) {
            if (v % p[j] == 0) {
                while (v % p[j] == 0) {
                    v /= p[j];
                    ++c[j];
                }
            }
        }
        
        // 预处理每个数字d对v的覆盖情况
        for (int j = 1; j < 10; ++j) {
            auto v = j;
            for (int k = 0; k < 4; ++k) {
                if (v % p[k] == 0) {
                    // 检查数字j是否包含足够的质因数p[k]
                    auto cnt = 0;
                    while (cnt <= c[k] && v % p[k] == 0) {
                        v /= p[k];
                        ++cnt;
                    }
                    if (cnt > c[k]) {
                        b[i][j] = -1;  // 数字j包含过多质因数p[k]
                        break;
                    }
                    if (cnt == c[k])
                        b[i][j] |= 1 << k;  // 标记覆盖情况
                }
            }
        }
    }
}

数位DP核心

long long recur(int idx, int mask, int rem, int f, int s, int v, int t, vector<int> &ds) {
    // idx: 当前处理到的位数
    // mask: 已选数字的质因数覆盖状态
    // rem: 当前数模v的余数
    // f: 是否已经小于上界
    // s: 是否已经开始选择非零数字
    // v: 当前考虑的LCM值
    // t: 目标覆盖状态
    // ds: 数字的各位数字
    
    if (idx >= int(ds.size()))
        return ((s && rem == 0 && mask == t) ? 1 : 0);
    
    auto &res = dp[idx][mask][rem][f][s];
    if (res != -1) return res;
    
    res = 0;
    for (int i = 0; i < 10; ++i) {
        if (!f && i > ds[idx]) break;      // 超过上界
        if (i == 0 && s) continue;         // 不能有前导零
        if (b[v][i] == -1) continue;       // 数字i不满足条件
        
        auto ret = recur(idx + 1, 
                        mask | b[v][i],           // 更新覆盖状态
                        (rem * 10 + i) % v,       // 更新余数
                        (i < ds[idx] ? 1 : f),    // 更新上界标志
                        (i > 0 ? 1 : s),          // 更新开始标志
                        v, t, ds);
        res += ret;
    }
    return res;
}

主计算函数

long long calc(long long n) {
    if (n <= 0) return 0;
    if (mem.find(n) != mem.end()) return mem[n];
    
    vector<int> ds;
    get_digits(n, ds);  // 将n分解为数字数组
    
    vector<bool> f(m + 1);
    long long res = 0;
    
    // 枚举所有可能的数字集合（状态压缩）
    for (int i = 0; i < 256; ++i) {
        auto v = 1;
        // 计算数字集合对应的LCM
        for (int j = 0; j < 8; ++j)
            if (i & (1 << j))
                v = v * (j + 2) / __gcd(v, j + 2);
        
        if (f[v]) continue;  // 去重
        f[v] = true;
        
        // 计算目标覆盖状态
        auto mask = 0;
        for (int i = 0; i < 4; ++i)
            if (v % p[i] == 0)
                mask |= 1 << i;
        
        // 初始化DP数组
        for (int i = 0; i < int(ds.size()); ++i)
            for (int j = 0; j < 16; ++j)
                for (int k = 0; k < v; ++k)
                    memset(dp[i][j][k], 255, sizeof(dp[i][j][k]));
        
        auto ret = recur(0, 0, 0, 0, 0, v, mask, ds);
        res += ret;
    }
    
    mem[n] = res;
    return res;
}

算法复杂度

• 预处理：$O(m \times 10)$，其中 $m = 2520$
• 数位DP：$O(\text{位数} \times 16 \times m \times 2 \times 2 \times 10)$
• 状态数：最多 $20 \times 16 \times 2520 \times 2 \times 2 \approx 3.2 \times 10^6$ 个状态