查看源代码：
palindrome-number-count.md

---
title: 答网友：求 [a, b] 间的回文数
createTime: 2024/10/27
categories:
    - IT
tags:
    - OI
    - maths
---

[原帖传送门](https://www.luogu.com.cn/discuss/976900)

依照数据范围，可以有 3 个优化等级。  
注：这里我们将回文数的处理视为 $\mathrm{O}(\log n)$

1. 枚举前半段，检查全回文数是否在 $[a,b]$ 里面，$\mathrm{O}(\sqrt n \log n)$

2. 注意到如果 $a=1$ 的话可以二分查找最大的符合条件的前半段。奇数位和偶数位的最大符合前半段不同，所以找完奇数前半段数 $a_i$ 之后在在 $[1, a_1]$ 找 $a_2$ 即可。  
当 $a\ne 1$ 时，只需要算出 $[1,b]$ 内的回文数数量，然后减去 $[1,a-1]$ 内的回文数即可。$\mathrm{O}(\log^2 n)$.

3. 又注意到最大的符合条件的同奇偶前半段一定是 $b$ 的前半段或其减 1，不同奇偶一定形如 $99\cdots9$.  
e.g. 1234: 分别为 1221 和 999.  
于是用 $\mathrm{O}(\log n)$ 判断最大的符合条件的前半段。和 2 一样，也是用 $[1,b]$ 的答案减 $[1,a-1]$ 的答案。