[NICA #2] 回溯的雨

Luogu

IDLGB3830

Time1000ms

Memory128MB

DifficultyP2

数学O2优化

小 Ran 有两个正整数 $x,y$，她还有两个长度为 $n$ 的正整数序列 $a$ 与 $c$ 满足 $a_ix+y=c_i$ （$1\le i\le n$）。很可惜的是，她忘记了所有 $a_i$ 的值与 $y$ 的值。她给你了 $x$ 的值与序列 $c$，并希望你能还原出一组 $y$ 的值与序列 $a$ 使得原先的条件被满足。当然，可能存在很多组这样的解，所以她希望你能最大化 $y$ 的值并输出它（注意到你并不需要输出 $a$ 序列）。如果不能还原出这样一组数，请输出 $-1$ 来报告无解。 ## Input 第一行两个正整数 $n$ 与 $x$，含义同题目描述。第二行 $n$ 个正整数，描述数组 $c$，其中第 $i$ 个数即为 $c_i$。 ## Output 输出一个正整数，代表你还原出的最大的 $y$ 的值。如果不能还原出这样一组正整数，则输出 $-1$。 [samples] ## Note 数据保证，$1 \leq n \leq 10^5$，$1 \leq x \leq 10^{12}$，$1 \leq c_i \leq 10^{18}$。

Samples

Input #1

5 2
4 6 8 10 12

Output #1

Input #2

5 2
3 6 9 12 15

Output #2

-1

API Response (JSON)

{
  "problem": {
    "name": "[NICA #2] 回溯的雨",
    "description": {
      "content": "小 Ran 有两个正整数 $x,y$，她还有两个长度为 $n$ 的正整数序列 $a$ 与 $c$ 满足 $a_ix+y=c_i$ （$1\\le i\\le n$）。 很可惜的是，她忘记了所有 $a_i$ 的值与 $y$ 的值。她给你了 $x$ 的值与序列 $c$，并希望你能还原出一组 $y$ 的值与序列 $a$ 使得原先的条件被满足。 当然，可能存在很多组这样的解，所以她希望你能最大化 $y$ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3830"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 Ran 有两个正整数 $x,y$，她还有两个长度为 $n$ 的正整数序列 $a$ 与 $c$ 满足 $a_ix+y=c_i$ （$1\\le i\\le n$）。\n\n很可惜的是，她忘记了所有 $a_i$ 的值与 $y$ 的值。她给你了 $x$ 的值与序列 $c$，并希望你能还原出一组 $y$ 的值与序列 $a$ 使得原先的条件被满足。\n\n当然，可能存在很多组这样的解，所以她希望你能最大化 $y$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments