4415. [ICPC2026河南省赛]数学的大厦崩塌了

【题目描述】

小 C 正在学分数约分，他吃惊地发现，计算 $\frac{16}{64}$ 时，将分子和分母中同时出现的数字 $6$ “删去”，竟然得到了正确的约分结果 $\frac{1}{4}$。他又随手试了几个，发现类似的例子都是正确的：

小 C 感觉数学的大厦崩塌了，他想知道在给定范围内，还有多少个这样的分数可以让数学的大厦崩塌。

形式化地说，对于给定的正整数 $n$，请你计算有多少个四元组 $(A,B,a,b)$ 满足以下全部条件：

• $1 \le A \le B \le n$，即约分前要求分母在 $n$ 范围内且 $\frac{A}{B}$ 是一个真分数；
• $1 \le a \lt b$，即约分后 $\frac{a}{b}$ 是一个真分数；
• $A,B,a,b$ 均不含前导零；
• $A \neq a$，即不能什么都不删；
• $A*b=B*a$，即删减后分数的值与原分数相等；
• $a$ 和 $b$ 没有公共数字，即删减后的分数不可继续删减；
• 对于每个数字 $d \in \{0,1,\cdots,9\}$，$d$ 在 $A$ 中的出现次数 $-$ $d$ 在 $B$ 中的出现次数 $=$ $d$ 在 $a$ 中的出现次数 $-$ $d$ 在 $b$ 中的出现次数，即分子分母删去的数字完全相同；
• 若将 $A,B,a,b$ 视为字符串，满足 $a$ 是 $A$ 的子序列，$b$ 是 $B$ 的子序列；

【输入格式】

一个正整数 $n$（$1 \le n \le 10000$），表示$B$的取值范围上界。

【输出格式】

输出一行一个整数，表示满足条件的四元组 $(A,B,a,b)$ 的数量。

【输入样例 1】

40

【输出样例 1】

6

【输入样例 2】

100

【输出样例 2】

48

【输入样例 3】

10000

【输出样例 3】

218429

【样例说明】

对于第一个样例，满足条件的六个四元组分别是：

$$ \frac{10}{20} = \frac{1}{2} \quad \frac{10}{30} = \frac{1}{3} \quad \frac{20}{30} = \frac{2}{3} \quad \frac{10}{40} = \frac{1}{4} \quad \frac{20}{40} = \frac{2}{4} \quad \frac{30}{40} = \frac{3}{4} $$

对于第二个样例，除了 $A$ 和 $B$ 均为 $10$ 的倍数的情况，有四种情况比较特殊：

$$ \frac{16}{64} = \frac{1}{4} \quad \frac{26}{65} = \frac{2}{5} \quad \frac{19}{95} = \frac{1}{5} \quad \frac{49}{98} = \frac{4}{8} $$

请注意，同一个 $\frac{A}{B}$ 可能通过不同的删减方式得到不同的合法四元组。例如 $\frac{3163}{6326}$，可以删减为 $\frac{13}{26}$ 或 $\frac{31}{62}$，因此四元组 $(3163,6326,13,26)$ 和 $(3163,6326,31,62)$ 要分别计数。

以下是一些不合法的例子和原因：

• $\frac{604}{6040}$：虽然可以通过删减得到 $\frac{4}{40}$ 且 $\frac{604}{6040} = \frac{4}{40}$，但是 $\frac{4}{40}$ 有公共数字 $4$，仍可继续删减，不满足条件。
• $\frac{597}{995}$：虽然可以通过删减得到 $\frac{57}{95}$ 且 $\frac{597}{995}=\frac{57}{95}$，但是 $\frac{57}{95}$ 有公共数字 $5$，仍可继续删减，不满足条件。
• $\frac{893}{940}$：虽然 $\frac{893}{940}=\frac{38}{40}$，但将 $3383$ 视为字符串，它不是 $893$ 的子序列，不满足条件。

【来源】

ICPC 2026 河南省赛。