#P18157. Prefix Divisible by Suffix

Prefix Divisible by Suffix

Prefix Divisible by Suffix

给定两个正整数 n,cn,c。

考虑正整数 xx 的十进制表示 x=(xk−1xk−2…x1x0)10x=(x_{k-1}x_{k-2}\dots x_1x_0)_{10}(无前导零)。若存在 0<i≤k−10<i\le k-1,把 xx 分成非空前缀

p=(xk−1…xi)10p=(x_{k-1}\dots x_i)_{10}

与非空后缀

s=(xi−1…x0)10,s=(x_{i-1}\dots x_0)_{10},

使得 pp 能被 s+cs+c 整除,则称 xx 是好数。注意 xi−1=0x_{i-1}=0 是允许的。

求 11 到 nn 之间好数的个数。

输入格式

一行两个正整数 n,cn,c(1≤n≤10141\le n\le 10^{14},1≤c≤1041\le c\le 10^4)。

输出格式

输出一个整数,表示好数的个数。

样例 1

输入:

20 1

输出:

2

好数为10、20。

样例 2

输入:

111 4

输出:

9

好数为40、51、62、73、80、84、95、101、106。

样例 3

输入:

1111 10

输出:

75

样例 4

输入:

1000000 7

输出:

111529