You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定正整数 $n$ 和两个一位正整数 $a,b$ ，有以下定义：

• 一个正整数是 $\texttt{laz}$ 数，当且仅当其十进制表示中（不含前导零）仅出现 $a$ 或 $b$ 。

求 $\{1,2,\ldots,n\}$ 中 $\texttt{laz}$ 数的个数。

输入格式

输入由一行构成，包含三个正整数，分别为 $n,a,b\,(1 \le n \le 9 \times 10^8,\,1 \le a,b \le 9)$，含义如题所示。

输出格式

输出一行一个整数，表示 $\{1,2,\ldots,n\}$ 中 $\texttt{laz}$ 数的个数。

输入输出样例 #1

输入 #1

200 1 2

输出 #1

10

说明/提示

对于样例，所有数码中仅出现1或2的数从小到大依次为：

$1,2,11,12,21,22,111,112,121,122,211,\ldots$

其中在 $\{1,2,\ldots,200\}$ 中的有 $10$ 个（1,2,11,12,21,22,111,112,121,122），故答案输出10。

提示： 本题 $n$ 的数据范围较大，$\Omega(n)$ 复杂度的程序无法通过，即你无法使用先枚举 $[1,n]$ 之间的整数再判断的算法通过本题。