C. Coprimes

Codeforces

IDCF10149C

Time3000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

A. Tuttu (a distant relative of W. Tutte) is a young mathematician with a promising future. As a child, he was very lonely, since he had no siblings nor cousins. One of his earliest Christmas gifts was a Number Theory book. That is the reason he focused on studying this area since a very early age. He was very interested in coprimes, but he could not solve the following problem and he asked you to help him. Given a sequence of N positive integers, we want to answer M queries. Each query is represented by two indices. He would like to know if there exists a pair of relatively prime numbers in the sequence whose positions are between the given indices. The first line has the numbers N and M separated by a space. The second line contains N positive integers a1, a2, ..., aN separated by a space. Then there are M lines, each one containing two integers, and r, separated by a space, encoding a query. For each one of the queries you should print "S" (without the double quotes) if there is a pair of relatively prime integers between (including) the sequence positions indexed by and r, or "N" otherwise. Two numbers are called coprime (or relatively prime) if their greatest common divisor is the number 1. ## Input The first line has the numbers N and M separated by a space. The second line contains N positive integers a1, a2, ..., aN separated by a space. Then there are M lines, each one containing two integers, and r, separated by a space, encoding a query. 2 ≤ N ≤ 5·104 1 ≤ M ≤ 2·105 1 ≤ ai ≤ 5·105, 1 ≤ i ≤ N ## Output For each one of the queries you should print "S" (without the double quotes) if there is a pair of relatively prime integers between (including) the sequence positions indexed by and r, or "N" otherwise. [samples] ## Note Two numbers are called coprime (or relatively prime) if their greatest common divisor is the number 1.

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $, let $ (a_k, b_k, c_k) \in \mathbb{Z}^3 $ denote the lengths of the three distinct roads. **Constraints** 1. $ 1 \leq T \leq 10^5 $ 2. For each $ k \in \{1, \dots, T\} $: $ 1 \leq a_k, b_k, c_k \leq 10^9 $ and $ a_k, b_k, c_k $ are distinct. **Objective** For each test case $ k $, output: - "First" if $ a_k = \min(a_k, b_k, c_k) $, - "Second" if $ b_k = \min(a_k, b_k, c_k) $, - "Third" if $ c_k = \min(a_k, b_k, c_k) $.

API Response (JSON)

{
  "problem": {
    "name": "C. Coprimes",
    "description": {
      "content": "A. Tuttu (a distant relative of W. Tutte) is a young mathematician with a promising future. As a child, he was very lonely, since he had no siblings nor cousins. One of his earliest Christmas gifts wa",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10149C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A. Tuttu (a distant relative of W. Tutte) is a young mathematician with a promising future. As a child, he was very lonely, since he had no siblings nor cousins. One of his earliest Christmas gifts wa...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ (a_k, b_k, c_k) \\in \\mathbb{Z}^3 $ denote the lengths of the three distinc...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments