一、问题分析与数学建模

1.1 问题本质

这是一道数学规律 + 枚举优化问题，核心在于理解荒谬度的计算规则并找到最优策略。

问题形式化

荒谬度计算规则：

1. 去除价格 $p$ 末尾的所有 0
2. 设去除 0 后的长度为 $a$
3. 如果此时末位是 5，荒谬度 = $2a - 1$；否则荒谬度 = $2a$

目标：在区间 $[L, R]$ 中找到荒谬度最小的价格，若有多个则选择数值最小的。

---

1.2 核心数学观察

观察 1：荒谬度的数学性质

命题 1：去除尾部 0 后，数字位数越少，荒谬度越低。

证明： 设去除 0 后的长度为 $a$，则荒谬度最多为 $2a$，最少为 $2a-1$。

显然，$a$ 越小，荒谬度越低。✓

---

命题 2：对于位数相同的数，末位为 5 的荒谬度最低。

证明：

• 末位为 5：荒谬度 = $2a - 1$
• 末位非 5：荒谬度 = $2a$

显然 $2a - 1 < 2a$。✓

---

观察 2：特殊数字的荒谬度

引理 1：10 的幂次的荒谬度恒为 2。

证明： 对于 $10^k$（如 10, 100, 1000, 10000...）：

1. 去除所有尾部 0 后得到 1
2. 长度 $a = 1$
3. 末位不是 5，荒谬度 = $2 \times 1 = 2$

例子：

• $10 \to 1$，长度 1，荒谬度 = 2
• $100 \to 1$，长度 1，荒谬度 = 2
• $1000 \to 1$，长度 1，荒谬度 = 2
• $10000 \to 1$，长度 1，荒谬度 = 2

---

引理 2：$5 \times 10^k$ 的荒谬度恒为 1。

证明： 对于 $5 \times 10^k$（如 5, 50, 500, 5000...）：

1. 去除所有尾部 0 后得到 5
2. 长度 $a = 1$
3. 末位是 5，荒谬度 = $2 \times 1 - 1 = 1$

例子：

• $5 \to 5$，长度 1，荒谬度 = 1 ✓
• $50 \to 5$，长度 1，荒谬度 = 1 ✓
• $500 \to 5$，长度 1，荒谬度 = 1 ✓
• $5000 \to 5$，长度 1，荒谬度 = 1 ✓

---

定理 1：在所有正整数中，荒谬度的最小值为 1，由 $5 \times 10^k$ 达到。

证明：

• 最小位数为 1
• 位数为 1 时，荒谬度最小为 $2 \times 1 - 1 = 1$（末位为 5）
• 因此全局最小荒谬度为 1 ✓

---

观察 3：荒谬度分布规律

定理 2：荒谬度为 1 的数：$\{5, 50, 500, 5000, \ldots\}$

定理 3：荒谬度为 2 的数：$\{1, 2, 3, 4, 6, 7, 8, 9, 10, 20, \ldots, 90, 100, 200, \ldots, 10000, \ldots\}$

规律：

• 荒谬度 1：$5 \times 10^k$
• 荒谬度 2：$d \times 10^k$（$d \in \{1,2,3,4,6,7,8,9\}$）
• 荒谬度 3：$d5 \times 10^k$（$d \in \{1,2,\ldots,9\}$，如 15, 25, 35...）
• 荒谬度 4：两位非 5 结尾的数（如 11, 12, 13...）

---

1.3 贪心策略

策略：优先查找区间内荒谬度尽可能低的特殊数字。

优先级（从高到低）：

1. $5 \times 10^k$（荒谬度 1）
2. $10^k$（荒谬度 2）
3. $d \times 10^k$（荒谬度 2）
4. 其他数字（荒谬度 ≥ 3）

关键观察：10000 的整数倍至少有 4 个尾部 0，去除后位数很少，荒谬度较低。

---

二、算法设计

2.1 朴素算法

思路：枚举区间 $[L, R]$ 内所有整数，计算荒谬度，取最小值。

时间复杂度：$O((R - L) \times \log R)$

问题：当 $R - L$ 很大时（最多 $10^9$），会超时。

---

2.2 分块优化算法

核心思想：

• 当区间较小时，直接暴力枚举
• 当区间较大时，利用荒谬度规律，跳过大量不可能的候选

分块策略： 设块大小 $\text{len} = 10000$。

将区间 $[L, R]$ 分为三部分：

1. 左边界：$[L, \text{第一个 len 的整数倍})$
2. 中间块：$[\text{第一个 len 的整数倍}, \text{最后一个 len 的整数倍}]$，只检查 len 的整数倍
3. 右边界：$(\text{最后一个 len 的整数倍}, R]$

数学依据：

定理 4：在长度足够大的区间内，必然存在 10000 的整数倍，其荒谬度不超过 2。

证明：

• 10000 的整数倍至少有 4 个尾部 0
• 去除后得到形如 $d$ 或 $d \times 10^k$ 的数
• 荒谬度 = 2（最多）

因此，只需检查 10000 的整数倍，即可快速找到低荒谬度的候选。✓

---

2.3 时间复杂度分析

小区间（$R - L \le \text{len}$）：

$$T = O(R - L) = O(10000)$$

大区间（$R - L > \text{len}$）：

• 左边界枚举：$O(\text{len}) = O(10000)$
• 中间跳跃：$O(\frac{R - L}{\text{len}}) = O(\frac{10^9}{10^4}) = O(10^5)$
• 右边界枚举：$O(\text{len}) = O(10000)$

总复杂度：

$$T = O(\text{len} + \frac{R - L}{\text{len}} + \text{len}) = O(10^5) $$

对于 $T \le 100$ 组测试，总复杂度 $O(10^7)$，可以接受。✓

---

三、代码模块详解

模块 1：荒谬度计算函数

int han(int x) {  // 计算荒谬值的函数
    int res = 0, last;
    
    // 步骤1: 去除末尾的所有0
    while (x && x % 10 == 0)
        x /= 10;
    
    // 步骤2: 记录去除0后的末位数字
    last = x % 10;
    
    // 步骤3: 计算位数 × 2
    while (x) {
        res += 2;
        x /= 10;
    }
    
    // 步骤4: 如果末位是5，荒谬度减1
    if (last == 5)
        res--;
    
    return res;
}

详细解析：

第一步：去除尾部 0

while (x && x % 10 == 0)
    x /= 10;

• x % 10 == 0：判断末位是否为 0
• 不断除以 10，直到末位不是 0

示例：

• $850 \to 85$（去除 1 个 0）
• $1000 \to 1$（去除 3 个 0）
• $5000 \to 5$（去除 3 个 0）

第二步：记录末位

last = x % 10;

• 保存去除 0 后的末位数字（用于判断是否为 5）

第三步：计算位数

while (x) {
    res += 2;
    x /= 10;
}

• 每除以 10 一次，位数减 1
• 荒谬度增加 2

示例：

• $85$：2 位，$res = 4$
• $1$：1 位，$res = 2$
• $5$：1 位，$res = 2$

第四步：末位为 5 的修正

if (last == 5)
    res--;

• 如果末位是 5，荒谬度减 1

---

模块 2：主查找函数

int find(int l, int r) {
    int ans, mi = 0x3f3f3f3f;  // mi 初始化为无穷大
    
    // 分情况处理...
}

变量说明：

• ans：答案（最小荒谬度对应的价格）
• mi：当前找到的最小荒谬度
• 0x3f3f3f3f：一个很大的数（约 $10^9$）

---

模块 3：小区间处理

if (r - l <= len) {  // 区间长度小的，暴力枚举
    for (int i = l; i <= r; i++) {
        int x = han(i);
        
        if (x < mi)
            mi = x, ans = i;
    }
}

策略：当区间长度不超过 10000 时，直接暴力枚举所有价格。

时间复杂度：$O(R - L)$，最多 10000 次。

为什么暴力：

• 区间较小时，暴力枚举简单高效
• 避免复杂的分块逻辑

---

模块 4：大区间分块处理

第一步：对齐边界

int i = l, j = r;

// 将 i 跳到第一个 len 的整数倍
while (i % len)
    i++;

// 将 j 跳到最后一个 len 的整数倍
while (j % len)
    j--;

目的：找到区间内第一个和最后一个 10000 的整数倍。

示例：

l = 998, r = 12345, len = 10000

i = 998
  → i % 10000 = 998 ≠ 0
  → i++ → 999
  → i % 10000 = 999 ≠ 0
  → ...
  → i = 10000 (第一个整数倍)

j = 12345
  → j % 10000 = 2345 ≠ 0
  → j-- → 12344
  → ...
  → j = 10000 (最后一个整数倍)

对齐后的区间划分：

[l, i)         → 左边界，暴力枚举
[i, j]         → 中间块，跳跃检查
(j, r]         → 右边界，暴力枚举

---

第二步：处理左边界

for (int k = l; k < i; k++) {  // 两边多余的暴力计算
    int x = han(k);
    
    if (x < mi)
        mi = x, ans = k;
}

处理范围：$[L, i)$，即第一个 10000 整数倍之前的所有数。

最多枚举：不超过 10000 个数。

---

第三步：跳跃检查中间块

for (int k = i / len; k <= j / len; k++) {  // 中间每次跳len的长度
    int x = han(k);  // 注意：计算 k 的荒谬度
    
    if (x < mi)
        mi = x, ans = k * len;  // 答案是 k * len
}

关键点解析：

为什么检查 k 而不是 k * len？

这是代码中最巧妙的地方！

数学原理：

• $k \times \text{len} = k \times 10000$
• 10000 有 4 个尾部 0
• 去除 $k \times 10000$ 的尾部 0，等价于去除 $k$ 的尾部 0 再额外去除 4 个 0

但重要的是：

• $k$ 的荒谬度 = 去除 $k$ 尾部 0 后的荒谬度
• $k \times 10000$ 的荒谬度 = 去除所有尾部 0 后的荒谬度

示例：

k = 1:
  han(1) = 2
  1 × 10000 = 10000 → 去除0 → 1，荒谬度 = 2 ✓

k = 5:
  han(5) = 1
  5 × 10000 = 50000 → 去除0 → 5，荒谬度 = 1 ✓

k = 10:
  han(10) = han(1) = 2
  10 × 10000 = 100000 → 去除0 → 1，荒谬度 = 2 ✓

k = 15:
  han(15) = han(15) = 3 (去除0后是15，2位，末位5)
  15 × 10000 = 150000 → 去除0 → 15，荒谬度 = 3 ✓

结论：han(k) 就是 han(k * len) 的值！✓

为什么是 k * len？

• k 只是索引
• 真正的价格是 k * len = k * 10000
• 所以答案要乘以 len

---

第四步：处理右边界

for (int k = j + 1; k <= r; k++) {
    int x = han(k);
    
    if (x < mi)
        mi = x, ans = k;
}

处理范围：$(j, R]$，即最后一个 10000 整数倍之后的所有数。

最多枚举：不超过 10000 个数。

---

模块 5：主函数

int main() {
    scanf("%d", &n);
    len = 10000;  // 设置块大小
    int l, r;
    
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &l, &r);
        printf("%d\n", find(l, r));
    }
    
    return 0;
}

参数选择：

• len = 10000：经验值，平衡跳跃次数和边界枚举

为什么选 10000？

1. 10000 = $10^4$，有 4 个尾部 0
2. 10000 的整数倍荒谬度不超过 2
3. 既不太大（边界枚举少），也不太小（跳跃次数少）

---

四、正确性证明

4.1 算法正确性

定理 5：算法保证找到最小荒谬度的价格。

证明：

情况 1：小区间（$R - L \le 10000$）

• 枚举了所有价格
• 必然找到最小荒谬度 ✓

情况 2：大区间（$R - L > 10000$）

• 左边界：枚举了 $[L, i)$ 的所有价格
• 中间块：枚举了所有 10000 整数倍的价格
• 右边界：枚举了 $(j, R]$ 的所有价格

关键：需要证明中间块中，非 10000 整数倍的价格不可能更优。

引理 3：在区间 $[i, j]$ 中，10000 整数倍的价格荒谬度不超过其他价格。

证明：

• 设 $p \in [i, j]$ 不是 10000 的整数倍
• $p$ 至多有 3 个尾部 0（否则是 10000 的整数倍）
• 去除尾部 0 后，$p$ 的位数至少为 $\log_{10}(p / 10^3)$

设 $q = k \times 10000$ 是最接近 $p$ 的 10000 整数倍：

• $q$ 至少有 4 个尾部 0
• 去除尾部 0 后，$q$ 的位数为 $\log_{10}(k)$

比较：

• 当 $k < 1000$ 时，$\log_{10}(k) < 3 \le \log_{10}(p / 10^3)$
• 因此 $q$ 的荒谬度不超过 $p$

所以只需检查 10000 的整数倍即可。✓

---

4.2 字典序最小性

定理 6：当荒谬度相同时，算法返回数值最小的价格。

证明：

• 枚举顺序：从小到大（$l \to r$）
• 更新条件：if (x < mi)（严格小于）
• 因此，相同荒谬度时，先遇到的（更小的）会被选中 ✓

---

五、样例验证

样例 1：$L = 998, R = 1002$

区间长度：$1002 - 998 = 4 < 10000$，使用暴力枚举。

枚举过程：

han(998) = han(998) = 6 (去除0后998，3位，末位8，荒谬度=6)
han(999) = 6 (去除0后999，3位，末位9，荒谬度=6)
han(1000) = han(1) = 2 (去除0后1，1位，末位1，荒谬度=2) ✓
han(1001) = 8 (去除0后1001，4位，末位1，荒谬度=8)
han(1002) = 8 (去除0后1002，4位，末位2，荒谬度=8)

最小荒谬度：2，对应价格 1000 ✓

---

样例 2：$L = 998, R = 2002$

区间长度：$2002 - 998 = 1004 < 10000$，使用暴力枚举。

关键候选：

han(1000) = 2
han(2000) = 2

两者荒谬度相同，选择更小的 1000 ✓

---

样例 3：$L = 4000, R = 6000$

区间长度：$6000 - 4000 = 2000 < 10000$，使用暴力枚举。

关键候选：

han(4000) = han(4) = 2 (去除0后4，1位，末位4，荒谬度=2)
han(5000) = han(5) = 1 (去除0后5，1位，末位5，荒谬度=1) ✓
han(6000) = han(6) = 2 (去除0后6，1位，末位6，荒谬度=2)

最小荒谬度：1，对应价格 5000 ✓

---

六、复杂度分析总结

时间复杂度

单次查询：

• 小区间：$O(\min(R - L, 10000))$
• 大区间：$O(10000 + \frac{R - L}{10000})$

最坏情况（$R - L = 10^9$）：

$$T = O(10000 + \frac{10^9}{10000}) = O(10^5)$$

总复杂度（$T = 100$）：

$$T_{\text{total}} = O(100 \times 10^5) = O(10^7)$$

可以接受 ✓

---

空间复杂度

$$S = O(1)$$

只使用了常数个变量。

---

七、易错点与优化

7.1 易错点 1：块大小选择

问题：len 设置不当会影响效率。

• len 太小：跳跃次数过多
• len 太大：边界枚举过多

最优选择：$\text{len} = \sqrt{R - L}$（理论最优）

实践选择：$\text{len} = 10000$（经验值，效果很好）

---

7.2 易错点 2：中间块检查

错误写法：

for (int k = i; k <= j; k += len) {
    int x = han(k);  // 错误！应该检查 k/len
    if (x < mi)
        mi = x, ans = k;
}

正确写法：

for (int k = i / len; k <= j / len; k++) {
    int x = han(k);  // 检查 k 的荒谬度
    if (x < mi)
        mi = x, ans = k * len;  // 答案是 k*len
}

---

7.3 易错点 3：边界对齐

问题：没有正确对齐到 len 的整数倍。

错误：

int i = l, j = r;
// 忘记对齐

正确：

while (i % len) i++;
while (j % len) j--;

---

八、算法扩展

8.1 进一步优化

观察：在区间 $[L, R]$ 中：

1. 优先查找 $5 \times 10^k$（荒谬度 1）
2. 如果没有，查找 $10^k$（荒谬度 2）
3. 再查找其他 $d \times 10^k$（荒谬度 2）

直接计算法：

// 找最小的 5×10^k 在 [L,R] 中
for (int k = 0; k <= 10; k++) {
    int p = 5 * pow(10, k);
    if (L <= p && p <= R)
        return p;  // 荒谬度 1，最优
}

// 找最小的 10^k 在 [L,R] 中
for (int k = 1; k <= 10; k++) {
    int p = pow(10, k);
    if (L <= p && p <= R)
        return p;  // 荒谬度 2
}

// 否则使用分块法

---

8.2 相关问题

1. 最大荒谬度：改为求最大荒谬度
2. 第 k 小荒谬度：求第 k 小的荒谬度价格
3. 荒谬度和：求区间内所有价格的荒谬度之和

---

九、知识点总结

核心算法技巧

1. ✅ 分块思想（Blocking）

   • 大区间分块处理
   • 跳跃检查关键位置

2. ✅ 数学规律分析

   • 荒谬度的计算规律
   • 特殊数字的性质

3. ✅ 枚举优化

   • 小区间暴力
   • 大区间优化

4. ✅ 贪心策略

   • 优先检查低荒谬度的候选

---

十、总结

算法精髓

本题采用的分块 + 数学规律算法的核心思想：

1. 数学观察：发现 10 的幂次和 5×10 的幂次荒谬度最低
2. 分块优化：大区间只检查 10000 的整数倍
3. 边界处理：暴力检查边界附近的数
4. 贪心策略：优先选择荒谬度低的特殊数