D. Wet Shark and Smallest Number

Codeforces

IDCF10160D

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Today, Wet Shark was given a list of non-necessarily distinct prime integers, a1, a2, ...an. Wet Shark defines k as the smallest integer such that for 1 ≤ i ≤ n, k mod ai = ai - 1. Wet Shark also has an additional integer, o. Tell Wet Shark whether or not k is divisible by o. The first line contains one integer, n 1 ≤ n ≤ 100000. The second line consists of n space separated integers, the list of primes. Each prime ranges from 2 to 100000. The third line consists of the additional integer, o, ranging from 1 to 100000. If k is divisible by o, output "YES". Else, output "NO". ## Input The first line contains one integer, n 1 ≤ n ≤ 100000.The second line consists of n space separated integers, the list of primes. Each prime ranges from 2 to 100000.The third line consists of the additional integer, o, ranging from 1 to 100000. ## Output If k is divisible by o, output "YES". Else, output "NO". [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ n_k \in \mathbb{Z} $ denote the length of the array. - Let $ A_k = (a_{k,1}, a_{k,2}, \dots, a_{k,n_k}) $ be a sequence of positive integers. **Constraints** 1. $ 1 \le T \le 64 $ 2. For each $ k \in \{1, \dots, T\} $: - $ 1 \le n_k \le 5000 $ - $ 1 \le a_{k,i} \le 10^6 $ for all $ i \in \{1, \dots, n_k\} $ 3. $ \sum_{k=1}^{T} n_k \le 72000 $ **Objective** Count the number of valid queries $ (l, r) $ with $ 1 \le l \le r \le n_k $ such that in the subarray $ (a_{k,l}, a_{k,l+1}, \dots, a_{k,r}) $, **exactly one distinct value** occurs an odd number of times, and all other values occur an even number of times.

API Response (JSON)

{
  "problem": {
    "name": "D. Wet Shark and Smallest Number",
    "description": {
      "content": "Today, Wet Shark was given a list of non-necessarily distinct prime integers, a1, a2, ...an. Wet Shark defines k as the smallest integer such that for 1 ≤ i ≤ n, k mod ai = ai - 1. Wet Shark also ha",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10160D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Today, Wet Shark was given a list of non-necessarily distinct prime integers, a1, a2, ...an.\n\nWet Shark defines k as the smallest integer such that for 1 ≤ i ≤ n, k mod ai = ai - 1.\n\nWet Shark also ha...",
      "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\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the length of the array.  \n- Let $ A_k = (...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments