A. Buy a Shovel

Codeforces

IDCF732A

Time1000ms

Memory256MB

Difficulty—

brute forceconstructive algorithmsimplementationmath

English · Original

Chinese · Translation

Formal · Original

Polycarp urgently needs a shovel! He comes to the shop and chooses an appropriate one. The shovel that Policarp chooses is sold for _k_ burles. Assume that there is an unlimited number of such shovels in the shop. In his pocket Polycarp has an unlimited number of "10-burle coins" and exactly one coin of _r_ burles (1 ≤ _r_ ≤ 9). What is the minimum number of shovels Polycarp has to buy so that he can pay for the purchase without any change? It is obvious that he can pay for 10 shovels without any change (by paying the requied amount of 10-burle coins and not using the coin of _r_ burles). But perhaps he can buy fewer shovels and pay without any change. Note that Polycarp should buy at least one shovel. ## Input The single line of input contains two integers _k_ and _r_ (1 ≤ _k_ ≤ 1000, 1 ≤ _r_ ≤ 9) — the price of one shovel and the denomination of the coin in Polycarp's pocket that is different from "10-burle coins". Remember that he has an unlimited number of coins in the denomination of 10, that is, Polycarp has enough money to buy any number of shovels. ## Output Print the required minimum number of shovels Polycarp has to buy so that he can pay for them without any change. [samples] ## Note In the first example Polycarp can buy 9 shovels and pay 9·117 = 1053 burles. Indeed, he can pay this sum by using 10-burle coins and one 3-burle coin. He can't buy fewer shovels without any change. In the second example it is enough for Polycarp to buy one shovel. In the third example Polycarp should buy two shovels and pay 2·15 = 30 burles. It is obvious that he can pay this sum without any change.

Polycarp 急需一把铲子！他来到商店并选择了一把合适的铲子。Polycarp 选择的铲子售价为 $k$ 贝尔。假设商店中这种铲子的数量无限。 Polycarp 口袋里有无限多枚“10 贝尔硬币”和恰好一枚面值为 $r$ 贝尔的硬币（$1 ≤ r ≤ 9$）。 Polycarp 最少需要买多少把铲子，才能无需找零地支付？显然，他可以购买 10 把铲子而无需找零（仅使用 10 贝尔硬币，不使用面值为 $r$ 贝尔的硬币）。但也许他可以购买更少的铲子并仍能无需找零支付。注意，Polycarp 至少需要购买一把铲子。输入的单行包含两个整数 $k$ 和 $r$（$1 ≤ k ≤ 1000$, $1 ≤ r ≤ 9$）——分别表示一把铲子的价格和 Polycarp 口袋中不同于“10 贝尔硬币”的硬币面值。请记住，他拥有无限多枚 10 贝尔硬币，即 Polycarp 有足够的钱购买任意数量的铲子。请输出 Polycarp 为能无需找零支付而必须购买的最少铲子数量。在第一个例子中，Polycarp 可以购买 9 把铲子，支付 $9·117 = 1053$ 贝尔。事实上，他可以通过使用若干枚 10 贝尔硬币和一枚 3 贝尔硬币支付这个金额。他无法在无需找零的情况下购买更少的铲子。在第二个例子中，Polycarp 只需购买一把铲子即可。在第三个例子中，Polycarp 应购买两把铲子，支付 $2·15 = 30$ 贝尔。显然，他可以无需找零地支付这个金额。 ## Input 输入的单行包含两个整数 $k$ 和 $r$（$1 ≤ k ≤ 1000$, $1 ≤ r ≤ 9$）——分别表示一把铲子的价格和 Polycarp 口袋中不同于“10 贝尔硬币”的硬币面值。请记住，他拥有无限多枚 10 贝尔硬币，即 Polycarp 有足够的钱购买任意数量的铲子。 ## Output 请输出 Polycarp 为能无需找零支付而必须购买的最少铲子数量。 [samples] ## Note 在第一个例子中，Polycarp 可以购买 9 把铲子，支付 $9·117 = 1053$ 贝尔。事实上，他可以通过使用若干枚 10 贝尔硬币和一枚 3 贝尔硬币支付这个金额。他无法在无需找零的情况下购买更少的铲子。在第二个例子中，Polycarp 只需购买一把铲子即可。在第三个例子中，Polycarp 应购买两把铲子，支付 $2·15 = 30$ 贝尔。显然，他可以无需找零地支付这个金额。

**Definitions** Let $ k \in \mathbb{Z} $ be the price of one shovel in burles. Let $ r \in \{1, 2, \dots, 9\} $ be the denomination of the unique non-10-burle coin Polycarp holds. **Constraints** $ 1 \leq k \leq 1000 $, $ 1 \leq r \leq 9 $ **Objective** Find the minimum positive integer $ n \in \mathbb{Z}^+ $ such that the total cost $ nk $ can be paid exactly using an unlimited supply of 10-burle coins and at most one $ r $-burle coin. That is, $$ nk \equiv 0 \pmod{10} \quad \text{or} \quad nk \equiv r \pmod{10} $$

Samples

Input #1

117 3

Output #1

Input #2

237 7

Output #2

Input #3

15 2

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Buy a Shovel",
    "description": {
      "content": "Polycarp urgently needs a shovel! He comes to the shop and chooses an appropriate one. The shovel that Policarp chooses is sold for _k_ burles. Assume that there is an unlimited number of such shovels",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF732A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp urgently needs a shovel! He comes to the shop and chooses an appropriate one. The shovel that Policarp chooses is sold for _k_ burles. Assume that there is an unlimited number of such shovels...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 急需一把铲子！他来到商店并选择了一把合适的铲子。Polycarp 选择的铲子售价为 $k$ 贝尔。假设商店中这种铲子的数量无限。\n\nPolycarp 口袋里有无限多枚“10 贝尔硬币”和恰好一枚面值为 $r$ 贝尔的硬币（$1 ≤ r ≤ 9$）。\n\nPolycarp 最少需要买多少把铲子，才能无需找零地支付？显然，他可以购买 10 把铲子而无需找零（仅使用 10 贝尔硬币，不使...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ k \\in \\mathbb{Z} $ be the price of one shovel in burles.  \nLet $ r \\in \\{1, 2, \\dots, 9\\} $ be the denomination of the unique non-10-burle coin Polycarp holds.  \n\n**Constraints...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments