题目背景

ICPC2020 WF M

题目描述

A large shipment of doodads has just arrived, and each doodad has a suggested retail price of $b$ cents. You've noticed that consumers are much more likely to purchase goods when most of the trailing digits are the same. For example, items are more likely to be priced at $99$ cents rather than $57$ cents. So to make your goods more appealing, you've decided to sell your goods in bundles. To make a bundle, you choose a positive integer $k$, and sell $k$ doodads for $k \times b$ cents. With an appropriate choice of $k$ you can have a more pleasing price. For example, selling $57$-cent doodads in bundles of size $7$ means that each bundle sells for $399$ cents, which has two trailing $9$s, rather than no trailing $9$s of $57$. This idea of trailing $9$s can be generalized to any other trailing digit: bundles of $692$ $57$-cent doodads sell for $39\,444$ cents (three trailing $4$s) and bundles of one million doodads sell for $57\,000\,000$ cents (six trailing $0$s).

After a little thought, you realize that you do not want to make your bundles too large---not only can the price be excessive, but who really needs several million doodads? For any type of doodad, your marketing department has a maximum bundle price of $a$.

Given the price of a doodad, the desired trailing digit, and the maximum price of a bundle, write a program that optimizes the trailing digits.

输入格式

Input consists of a single line containing three integers $b$, $d$, and $a$, where $b$ ($1 \leq b < 10^{6}$) is the price of a doodad in cents, $d$ ($0 \leq d \leq 9$) is the desired trailing digit, and $a$ ($b \leq a < 10^{10\,000}$) is the maximum price of a bundle.

输出格式

Output the maximum number of consecutive occurrences of $d$ that can appear at the end of a bundle price, given that the price of the bundle cannot exceed $a$.

题目大意

题目描述

有一批货，每个价值 $b$ 元，可以把 $n$ 个货打包出售，价格是 $b \times n$ 元（前提是$b \times n\le a$），使末尾含有尽可能多的数字 $d$ ，求最多的 $d$ 数量。

输入格式

一行三个整数，$b$ , $d$ 和 $a$。

输出格式

一个整数，最多的 $d$ 数量。

说明/提示

对于全部数据，有 $1 \le b < 10^6$ , $0 \le d \le 9$ , $b \le a < 10^{10000}$

57 9 1000

2

57 4 40000

3

57 4 39000

2