A. Fake NP

Codeforces

IDCF805A

Time1000ms

Memory256MB

Difficulty—

greedymath

English · Original

Chinese · Translation

Formal · Original

Tavak and Seyyed are good friends. Seyyed is very funny and he told Tavak to solve the following problem instead of _longest-path_. You are given _l_ and _r_. For all integers from _l_ to _r_, inclusive, we wrote down all of their integer divisors except 1. Find the integer that we wrote down the maximum number of times. Solve the problem to show that it's not a _NP_ problem. ## Input The first line contains two integers _l_ and _r_ (2 ≤ _l_ ≤ _r_ ≤ 109). ## Output Print single integer, the integer that appears maximum number of times in the divisors. If there are multiple answers, print any of them. [samples] ## Note Definition of a divisor: [https://www.mathsisfun.com/definitions/divisor-of-an-integer-.html](https://www.mathsisfun.com/definitions/divisor-of-an-integer-.html) The first example: from 19 to 29 these numbers are divisible by 2: {20, 22, 24, 26, 28}. The second example: from 3 to 6 these numbers are divisible by 3: {3, 6}.

Tavak 和 Seyyed 是好朋友。Seyyed 非常有趣，他告诉 Tavak 解决以下问题，而不是 _longest-path_。给你 #cf_span[l] 和 #cf_span[r]。对于从 #cf_span[l] 到 #cf_span[r]（包含两端）的所有整数，我们写下它们的所有整数因子（除了 #cf_span[1]）。找出我们写下次数最多的那个整数。解决这个问题，以证明它不是一个 _NP_ 问题。第一行包含两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[2 ≤ l ≤ r ≤ 109]）。输出一个整数，该整数在所有因子中出现次数最多。如果有多个答案，输出任意一个即可。因子的定义：https://www.mathsisfun.com/definitions/divisor-of-an-integer-.html 第一个例子：从 #cf_span[19] 到 #cf_span[29]，能被 #cf_span[2] 整除的数是：#cf_span[{20, 22, 24, 26, 28}]。第二个例子：从 #cf_span[3] 到 #cf_span[6]，能被 #cf_span[3] 整除的数是：#cf_span[{3, 6}]。 ## Input 第一行包含两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[2 ≤ l ≤ r ≤ 109]）。 ## Output 输出一个整数，该整数在所有因子中出现次数最多。如果有多个答案，输出任意一个即可。 [samples] ## Note 因子的定义：https://www.mathsisfun.com/definitions/divisor-of-an-integer-.html 第一个例子：从 #cf_span[19] 到 #cf_span[29]，能被 #cf_span[2] 整除的数是：#cf_span[{20, 22, 24, 26, 28}]。第二个例子：从 #cf_span[3] 到 #cf_span[6]，能被 #cf_span[3] 整除的数是：#cf_span[{3, 6}]。

**Definitions** Let $ l, r \in \mathbb{Z} $ with $ 2 \leq l \leq r \leq 10^9 $. For each integer $ n \in [l, r] $, let $ D(n) = \{ d \in \mathbb{Z} \mid d \mid n, \, d > 1 \} $ be the set of integer divisors of $ n $ excluding 1. Let $ F(d) = \left| \left\{ n \in [l, r] \mid d \in D(n) \right\} \right| $ be the frequency of divisor $ d $ across all $ n \in [l, r] $. **Constraints** $ 2 \leq l \leq r \leq 10^9 $ **Objective** Find an integer $ d^* > 1 $ such that: $$ F(d^*) = \max_{d > 1} F(d) $$ If multiple such $ d^* $ exist, output any one.

Samples

Input #1

19 29

Output #1

Input #2

3 6

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Fake NP",
    "description": {
      "content": "Tavak and Seyyed are good friends. Seyyed is very funny and he told Tavak to solve the following problem instead of _longest-path_. You are given _l_ and _r_. For all integers from _l_ to _r_, inclus",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF805A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Tavak and Seyyed are good friends. Seyyed is very funny and he told Tavak to solve the following problem instead of _longest-path_.\n\nYou are given _l_ and _r_. For all integers from _l_ to _r_, inclus...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Tavak 和 Seyyed 是好朋友。Seyyed 非常有趣，他告诉 Tavak 解决以下问题，而不是 _longest-path_。\n\n给你 #cf_span[l] 和 #cf_span[r]。对于从 #cf_span[l] 到 #cf_span[r]（包含两端）的所有整数，我们写下它们的所有整数因子（除了 #cf_span[1]）。找出我们写下次数最多的那个整数。\n\n解决这个问题，以证明它不...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ l, r \\in \\mathbb{Z} $ with $ 2 \\leq l \\leq r \\leq 10^9 $.  \nFor each integer $ n \\in [l, r] $, let $ D(n) = \\{ d \\in \\mathbb{Z} \\mid d \\mid n, \\, d > 1 \\} $ be the set of integ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments