B. Vile Grasshoppers

Codeforces

IDCF937B

Time1000ms

Memory256MB

Difficulty—

brute forcemathnumber theory

English · Original

Chinese · Translation

Formal · Original

The weather is fine today and hence it's high time to climb the nearby pine and enjoy the landscape. The pine's trunk includes several branches, located one above another and numbered from 2 to _y_. Some of them (more precise, from 2 to _p_) are occupied by tiny vile grasshoppers which you're at war with. These grasshoppers are known for their awesome jumping skills: the grasshopper at branch _x_ can jump to branches . Keeping this in mind, you wisely decided to choose such a branch that none of the grasshoppers could interrupt you. At the same time you wanna settle as high as possible since the view from up there is simply breathtaking. In other words, your goal is to find the highest branch that cannot be reached by any of the grasshoppers or report that it's impossible. ## Input The only line contains two integers _p_ and _y_ (2 ≤ _p_ ≤ _y_ ≤ 109). ## Output Output the number of the highest suitable branch. If there are none, print _\-1_ instead. [samples] ## Note In the first sample case grasshopper from branch 2 reaches branches 2, 4 and 6 while branch 3 is initially settled by another grasshopper. Therefore the answer is 5. It immediately follows that there are no valid branches in second sample case.

今天天气晴朗，正是攀爬附近松树、欣赏风景的好时机。松树的树干包含若干枝干，自下而上编号为 #cf_span[2] 到 #cf_span[y]。其中一些枝干（具体而言，从 #cf_span[2] 到 #cf_span[p]）被与你为敌的微小蚱蜢占据。这些蚱蜢以惊人的跳跃能力著称：位于枝干 #cf_span[x] 的蚱蜢可以跳到枝干。考虑到这一点，你明智地决定选择一个蚱蜢无法打扰你的枝干。同时，你希望尽可能高地安顿下来，因为高处的景色令人叹为观止。换句话说，你的目标是找到最高的、无法被任何蚱蜢到达的枝干编号，或者说明不存在这样的枝干。仅一行包含两个整数 #cf_span[p] 和 #cf_span[y] #cf_span[(2 ≤ p ≤ y ≤ 109)]。请输出最高合适枝干的编号。如果不存在这样的枝干，请输出 _-1_。在第一个样例中，来自枝干 #cf_span[2] 的蚱蜢可以到达枝干 #cf_span[2]、#cf_span[4] 和 #cf_span[6]，而枝干 #cf_span[3] 最初已被另一只蚱蜢占据。因此答案是 #cf_span[5]。显然，在第二个样例中不存在合法的枝干。 ## Input 仅一行包含两个整数 #cf_span[p] 和 #cf_span[y] #cf_span[(2 ≤ p ≤ y ≤ 109)]。 ## Output 请输出最高合适枝干的编号。如果不存在这样的枝干，请输出 _-1_。 [samples] ## Note 在第一个样例中，来自枝干 #cf_span[2] 的蚱蜢可以到达枝干 #cf_span[2]、#cf_span[4] 和 #cf_span[6]，而枝干 #cf_span[3] 最初已被另一只蚱蜢占据。因此答案是 #cf_span[5]。显然，在第二个样例中不存在合法的枝干。

**Definitions** Let $ p, y \in \mathbb{Z} $ with $ 2 \leq p \leq y \leq 10^9 $. Let $ G = \{ x \in \mathbb{Z} \mid 2 \leq x \leq p \} $ be the set of initial grasshopper branches. A branch $ b \in \mathbb{Z} $ is *reachable* if there exists $ x \in G $ and $ k \in \mathbb{Z}^+ $ such that $ b = kx $. Let $ R = \bigcup_{x \in G} \{ kx \mid k \in \mathbb{Z}^+ \} $ be the set of all reachable branches. **Constraints** $ 2 \leq p \leq y \leq 10^9 $ **Objective** Find the maximum $ b \in \{2, 3, \dots, y\} $ such that $ b \notin R $. If no such $ b $ exists, output $-1$.

Samples

Input #1

3 6

Output #1

Input #2

3 4

Output #2

\-1

API Response (JSON)

{
  "problem": {
    "name": "B. Vile Grasshoppers",
    "description": {
      "content": "The weather is fine today and hence it's high time to climb the nearby pine and enjoy the landscape. The pine's trunk includes several branches, located one above another and numbered from 2 to _y_. ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF937B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The weather is fine today and hence it's high time to climb the nearby pine and enjoy the landscape.\n\nThe pine's trunk includes several branches, located one above another and numbered from 2 to _y_. ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "今天天气晴朗，正是攀爬附近松树、欣赏风景的好时机。\n\n松树的树干包含若干枝干，自下而上编号为 #cf_span[2] 到 #cf_span[y]。其中一些枝干（具体而言，从 #cf_span[2] 到 #cf_span[p]）被与你为敌的微小蚱蜢占据。这些蚱蜢以惊人的跳跃能力著称：位于枝干 #cf_span[x] 的蚱蜢可以跳到枝干 。\n\n考虑到这一点，你明智地决定选择一个蚱蜢无法打扰你的枝干。同...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ p, y \\in \\mathbb{Z} $ with $ 2 \\leq p \\leq y \\leq 10^9 $.  \nLet $ G = \\{ x \\in \\mathbb{Z} \\mid 2 \\leq x \\leq p \\} $ be the set of initial grasshopper branches.  \nA branch $ b \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments