C. Преобразование числа

Codeforces

IDCF10052C

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Гена и Петя поспорили на мороженое, кто из них двоих умнее. Для того, чтобы это выяснить Гена написал на доске целое положительное число N и хочет, чтобы Петя получил из него число M, выполняя следующую операцию. Разрешается представить число на доске в виде суммы двух натуральных чисел X и Y, а затем заменить его на произведение X и Y. Если Петя сможет получить число M, то он выиграет спор, в противном случае выиграет Гена. Гена хочет узнать, есть ли у Пети шанс выиграть или же победа Гены неизбежна. В единственной строке входных данных находятся целые числа N и M, разделенные пробелом (1 ≤ N, M ≤ 10 000). Выведите _YES_, если Петя может победить, и _NO_ — в противном случае. В первом примере, последовательность преобразований следующая: представить 5 как 2 + 3 и заменить на 6 = 2 × 3, затем представить 6 как 3 + 3 и заменить на 9 = 3 × 3. Во втором примере, число 2 можно представить только как 1 + 1, поэтому на доске будет записано число 1 = 1 × 1. Число 1 нельзя представить в виде суммы двух натуральных чисел, поэтому число 10 000 получить нельзя. Значит, победит Гена. ## Входные Данные В единственной строке входных данных находятся целые числа N и M, разделенные пробелом (1 ≤ N, M ≤ 10 000). ## Выходные Данные Выведите _YES_, если Петя может победить, и _NO_ — в противном случае. ## Примеры Входные данные5 9Выходные данныеYESВходные данные2 10000Выходные данныеNO ## Примечание В первом примере, последовательность преобразований следующая: представить 5 как 2 + 3 и заменить на 6 = 2 × 3, затем представить 6 как 3 + 3 и заменить на 9 = 3 × 3.Во втором примере, число 2 можно представить только как 1 + 1, поэтому на доске будет записано число 1 = 1 × 1. Число 1 нельзя представить в виде суммы двух натуральных чисел, поэтому число 10 000 получить нельзя. Значит, победит Гена. [samples]

**Definitions** Let $ N, M \in \mathbb{Z}^+ $ with $ 1 \leq N, M \leq 10000 $. **Operation** From a current number $ x \geq 2 $, one may replace it with $ x' = a \cdot b $, where $ a, b \in \mathbb{Z}^+ $ and $ a + b = x $. **Objective** Determine whether there exists a finite sequence of such operations starting from $ N $ that results in $ M $. **Question** Is $ M $ reachable from $ N $ via zero or more valid operations?

API Response (JSON)

{
  "problem": {
    "name": "C. Преобразование числа",
    "description": {
      "content": "Гена и Петя поспорили на мороженое, кто из них двоих умнее. Для того, чтобы это выяснить Гена написал на доске целое положительное число N и хочет, чтобы Петя получил из него число M, выполняя следующ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10052C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Гена и Петя поспорили на мороженое, кто из них двоих умнее. Для того, чтобы это выяснить Гена написал на доске целое положительное число N и хочет, чтобы Петя получил из него число M, выполняя следующ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $ with $ 1 \\leq N, M \\leq 10000 $.  \n\n**Operation**  \nFrom a current number $ x \\geq 2 $, one may replace it with $ x' = a \\cdot b $, where $ a, b \\in \\ma...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments