平安数(Safe Number)

题目描述

若一个整数在十进制下不含 $13$ 作为子串，则称它为平安数，例如 $123$ 是平安数，但 $2132$ 不是平安数。给定一个 $n$，请计算从 $1$ 到 $n$ 有多少个平安数。

输入格式

单个整数：表示 $n$。

输出格式

单个整数：表示 $1$ 到 $n$ 之间有多少整数的十进制表示不含 $13$ 子串。

样例输入 #1

20

样例输出 #1

19

样例输入 #2

200

样例输出 #2

188

说明：13、113以及130到139都不是平安数

数据范围

• 对于 30% 的数据：$1 \leq n \leq 10^6$；
• 对于 60% 的数据：$1 \leq n \leq 10^9$；
• 对于 100% 的数据：$1 \leq n \leq 2^{63}-1$。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐。

测试点分布