「POI2018 R3」完备数 题解

算法思路分析

这是一个数论计数问题，需要统计区间内满足「十进制位数 = 约数个数」的数字数量。

关键观察

设数字 $n$ 有 $k$ 位，则完备数条件为：$d(n) = k$，其中 $d(n)$ 是 $n$ 的约数个数。

约数个数函数的数学性质

如果 $n = p_1^{a_1} p_2^{a_2} \cdots p_m^{a_m}$，则：

$$d(n) = (a_1 + 1)(a_2 + 1)\cdots(a_m + 1)$$

核心算法：预计算 + 数学分类

算法框架

1. 线性筛预处理

void init() {
    for(int i = 2; i < N; ++i) {
        // 线性筛求最小质因子
        if(!book[i]) book[i] = i, p[++num] = i, ++sig[i];
        for(int j = 1; p[j]*i < N; ++j) {
            book[p[j]*i] = p[j];
            if(p[j] == book[i]) break;
        }
    }
    // 预计算1-7位数的完备数
}

2. 按位数分类处理

1-7位数：直接枚举计算

for(int t = 1, l = 0, r = 0; t <= 7; ++t) {
    l = r + 1, r = l * 10 - 1;  // t位数范围
    for(int i = l; i <= r; i++) {
        // 分解质因数计算d(i)，检查是否等于t
        if(d(i) == t) ans[i] = ans[i-1] + 1;
    }
}

8位数：特殊公式计算

int query8(int x) {
    // 处理形如 p^7, p^3*q, p*q*r 的数
    // 这些形式的数d(n)=8
}

9位数：特殊公式计算

int query9(int x) {
    // 处理形如 p^8, p^2*q^2*r 的数
    // 这些形式的数d(n)=9
}

数学分类细节

8位数的约数个数为8的情况

• $p^7$：$d(n) = 7+1 = 8$
• $p^3 \cdot q$：$d(n) = (3+1)(1+1) = 8$
• $p \cdot q \cdot r$：$d(n) = (1+1)^3 = 8$

9位数的约数个数为9的情况

• $p^8$：$d(n) = 8+1 = 9$
• $p^2 \cdot q^2 \cdot r$：$d(n) = (2+1)(2+1)(1+1) = 9$

复杂度分析

• 预处理：$O(N)$ 线性筛，$N = 1.7 \times 10^7$
• 查询：$O(1)$ 查询前缀和，特殊位数 $O(\text{素数个数})$

算法标签

主要分类

• 数论 ⭐⭐⭐⭐⭐
• 组合数学 ⭐⭐⭐⭐
• 预计算 ⭐⭐⭐⭐

技术子标签

• 线性筛 ⭐⭐⭐⭐
• 质因数分解 ⭐⭐⭐⭐
• 计数函数 ⭐⭐⭐⭐

问题类型

• 区间计数 ⭐⭐⭐⭐
• 特殊数筛选 ⭐⭐⭐⭐
• 数学优化 ⭐⭐⭐⭐

关键算法技巧

1. 线性筛法

// 同时记录最小质因子，便于快速分解
book[p[j]*i] = p[j];

2. 按位数分组

• 1-7位：直接暴力枚举
• 8位：数学公式计数
• 9位：数学公式计数

3. 前缀和优化

ans[i] = ans[i-1] + (mult == t);  // 前缀和统计

4. 数学公式推导

利用约数个数函数的乘性性质，枚举所有可能的质因数分解形式。

样例验证

样例1

输入: [9,11]
计算: query(11) - query(8) 
11: 2位数，d(11)=2 ✓
输出: 1

样例2

输入: [999,1010]
计算: query(1010) - query(998)
1003: 4位数，d(1003)=4 ✓
1006: 4位数，d(1006)=4 ✓  
1007: 4位数，d(1007)=4 ✓
输出: 3

算法优势

1. 高效性：预处理后 $O(1)$ 查询
2. 完备性：覆盖所有可能的完备数形式
3. 可扩展性：方法可推广到更多位数
4. 数学严谨：基于数论性质保证正确性

适用数据范围

• 子任务1-4：$b \leq 10^7$，直接预计算覆盖
• 子任务5-6：$b \leq 10^9$，结合数学公式处理大数

该解法通过数论分类和预计算优化，成功解决了大规模区间内的特殊数计数问题，展现了组合数学在算法竞赛中的深度应用。