B. Proper Nutrition

Codeforces

IDCF898B

Time1000ms

Memory256MB

Difficulty—

brute forceimplementationnumber theory

English · Original

Chinese · Translation

Formal · Original

Vasya has _n_ burles. One bottle of Ber-Cola costs _a_ burles and one Bars bar costs _b_ burles. He can buy any non-negative integer number of bottles of Ber-Cola and any non-negative integer number of Bars bars. Find out if it's possible to buy some amount of bottles of Ber-Cola and Bars bars and spend **exactly** _n_ burles. In other words, you should find two non-negative integers _x_ and _y_ such that Vasya can buy _x_ bottles of Ber-Cola and _y_ Bars bars and _x_·_a_ + _y_·_b_ = _n_ or tell that it's impossible. ## Input First line contains single integer _n_ (1 ≤ _n_ ≤ 10 000 000) — amount of money, that Vasya has. Second line contains single integer _a_ (1 ≤ _a_ ≤ 10 000 000) — cost of one bottle of Ber-Cola. Third line contains single integer _b_ (1 ≤ _b_ ≤ 10 000 000) — cost of one Bars bar. ## Output If Vasya can't buy Bars and Ber-Cola in such a way to spend exactly _n_ burles print «_NO_» (without quotes). Otherwise in first line print «_YES_» (without quotes). In second line print two non-negative integers _x_ and _y_ — number of bottles of Ber-Cola and number of Bars bars Vasya should buy in order to spend exactly _n_ burles, i.e. _x_·_a_ + _y_·_b_ = _n_. If there are multiple answers print any of them. Any of numbers _x_ and _y_ can be equal 0. [samples] ## Note In first example Vasya can buy two bottles of Ber-Cola and one Bars bar. He will spend exactly 2·2 + 1·3 = 7 burles. In second example Vasya can spend exactly _n_ burles multiple ways: * buy two bottles of Ber-Cola and five Bars bars; * buy four bottles of Ber-Cola and don't buy Bars bars; * don't buy Ber-Cola and buy 10 Bars bars. In third example it's impossible to but Ber-Cola and Bars bars in order to spend exactly _n_ burles.

Vasya 有 #cf_span[n] 卢布。一瓶 Ber-Cola 的价格是 #cf_span[a] 卢布，一根 Bars 巧克力棒的价格是 #cf_span[b] 卢布。他可以购买任意非负整数数量的 Ber-Cola 瓶子和任意非负整数数量的 Bars 巧克力棒。请判断是否有可能购买一定数量的 Ber-Cola 瓶子和 Bars 巧克力棒，使得总花费 *恰好* 为 #cf_span[n] 卢布。换句话说，你需要找到两个非负整数 #cf_span[x] 和 #cf_span[y]，使得 Vasya 可以购买 #cf_span[x] 瓶 Ber-Cola 和 #cf_span[y] 根 Bars 巧克力棒，并满足 #cf_span[x·a + y·b = n]；如果不存在这样的组合，请说明不可能。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 10 000 000]) — Vasya 拥有的钱数。第二行包含一个整数 #cf_span[a] (#cf_span[1 ≤ a ≤ 10 000 000]) — 一瓶 Ber-Cola 的价格。第三行包含一个整数 #cf_span[b] (#cf_span[1 ≤ b ≤ 10 000 000]) — 一根 Bars 巧克力棒的价格。如果 Vasya 无法通过购买 Bars 和 Ber-Cola 恰好花费 #cf_span[n] 卢布，请输出 «_NO_»（不含引号）。否则，第一行输出 «_YES_»（不含引号），第二行输出两个非负整数 #cf_span[x] 和 #cf_span[y] —— Vasya 为恰好花费 #cf_span[n] 卢布应购买的 Ber-Cola 瓶数和 Bars 巧克力棒根数，即满足 #cf_span[x·a + y·b = n]。如果有多个答案，输出任意一个即可。 #cf_span[x] 和 #cf_span[y] 均可以为 #cf_span[0]。在第一个示例中，Vasya 可以购买两瓶 Ber-Cola 和一根 Bars 巧克力棒，他将恰好花费 #cf_span[2·2 + 1·3 = 7] 卢布。在第二个示例中，Vasya 有多种方式恰好花费 #cf_span[n] 卢布：在第三个示例中，无法购买 Ber-Cola 和 Bars 巧克力棒以恰好花费 #cf_span[n] 卢布。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 10 000 000]) — Vasya 拥有的钱数。第二行包含一个整数 #cf_span[a] (#cf_span[1 ≤ a ≤ 10 000 000]) — 一瓶 Ber-Cola 的价格。第三行包含一个整数 #cf_span[b] (#cf_span[1 ≤ b ≤ 10 000 000]) — 一根 Bars 巧克力棒的价格。 ## Output 如果 Vasya 无法通过购买 Bars 和 Ber-Cola 恰好花费 #cf_span[n] 卢布，请输出 «_NO_»（不含引号）。否则，第一行输出 «_YES_»（不含引号），第二行输出两个非负整数 #cf_span[x] 和 #cf_span[y] —— Vasya 为恰好花费 #cf_span[n] 卢布应购买的 Ber-Cola 瓶数和 Bars 巧克力棒根数，即满足 #cf_span[x·a + y·b = n]。如果有多个答案，输出任意一个即可。#cf_span[x] 和 #cf_span[y] 均可以为 #cf_span[0]。 [samples] ## Note 在第一个示例中，Vasya 可以购买两瓶 Ber-Cola 和一根 Bars 巧克力棒，他将恰好花费 #cf_span[2·2 + 1·3 = 7] 卢布。在第二个示例中，Vasya 有多种方式恰好花费 #cf_span[n] 卢布：购买两瓶 Ber-Cola 和五根 Bars 巧克力棒；购买四瓶 Ber-Cola 且不买 Bars 巧克力棒；不买 Ber-Cola 且购买 #cf_span[10] 根 Bars 巧克力棒。在第三个示例中，无法购买 Ber-Cola 和 Bars 巧克力棒以恰好花费 #cf_span[n] 卢布。

**Definitions** Let $ n, a, b \in \mathbb{Z}^+ $ be given integers. **Constraints** $ 1 \leq n \leq 10^7 $, $ 1 \leq a \leq 10^7 $, $ 1 \leq b \leq 10^7 $. **Objective** Determine whether there exist non-negative integers $ x, y \in \mathbb{Z}_{\geq 0} $ such that: $$ a \cdot x + b \cdot y = n $$ If such $ x, y $ exist, output any pair $ (x, y) $; otherwise, output "NO".

Samples

Input #1

7
2
3

Output #1

YES
2 1

Input #2

100
25
10

Output #2

YES
0 10

Input #3

15
4
8

Output #3

NO

Input #4

9960594
2551
2557

Output #4

YES
1951 1949

API Response (JSON)

{
  "problem": {
    "name": "B. Proper Nutrition",
    "description": {
      "content": "Vasya has _n_ burles. One bottle of Ber-Cola costs _a_ burles and one Bars bar costs _b_ burles. He can buy any non-negative integer number of bottles of Ber-Cola and any non-negative integer number o",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF898B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vasya has _n_ burles. One bottle of Ber-Cola costs _a_ burles and one Bars bar costs _b_ burles. He can buy any non-negative integer number of bottles of Ber-Cola and any non-negative integer number o...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Vasya 有 #cf_span[n] 卢布。一瓶 Ber-Cola 的价格是 #cf_span[a] 卢布，一根 Bars 巧克力棒的价格是 #cf_span[b] 卢布。他可以购买任意非负整数数量的 Ber-Cola 瓶子和任意非负整数数量的 Bars 巧克力棒。\n\n请判断是否有可能购买一定数量的 Ber-Cola 瓶子和 Bars 巧克力棒，使得总花费 *恰好* 为 #cf_span[n] ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, a, b \\in \\mathbb{Z}^+ $ be given integers.  \n\n**Constraints**  \n$ 1 \\leq n \\leq 10^7 $,  \n$ 1 \\leq a \\leq 10^7 $,  \n$ 1 \\leq b \\leq 10^7 $.  \n\n**Objective**  \nDetermine whet...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments