[YDOI R1] Running

Luogu

IDLGP10183

Time2000ms

Memory512MB

DifficultyP2

数学O2优化最大公约数 gcd洛谷比赛

小 Z 在一条公路上跑步，公路上有 $n$ 个超市，第 $i$ 个超市的位置为 $a_i$。当小 Z 经过一个超市的时间为奇数时，他就会去逛超市，从而被同学拉爆。小 Z 最开始位于位置为 $0$ 的点。他会在每个单位时间向右跑 $v$ 个单位长度。请求出：能够使小 Z 经过 $n$ 个超市中每一个超市时，都不去逛超市的 $v$ 的最大值。规定 $v$ 必须是正整数，且小 Z 到达任意一个超市时，花费的时间必须为整数，换言之，你需要保证小 Z 到达任意一个超市的时间都是偶数。注意时间初始为 $0$。 ## Input 输入共 $n+1$ 行。第 $1$ 行，$1$ 个正整数 $n$。第 $2\sim n+1$ 行，每行 $1$ 个正整数，第 $i+1$ 行输入的正整数是 $a_i$。 ## Output 输出共 $1$ 行。输出符合条件的 $v$ 的最大值。如果无解则输出 $-1$。 [samples] ## Background 小 Z 要去跑步，他想开学后拉爆他的同学。 ## Note ### 【样例解释】对于样例 $1$，可以证明不存在符合要求的速度。对于样例 $2$，当 $v=5$ 时，到达第 $1\sim5$ 个超市的时间分别为 $2$，$4$，$6$，$8$，$10$，均为偶数，符合题目要求。可以证明不存在更快的符合要求的速度。 **本题采用捆绑测试**。 |子任务编号|$n\le$|$a_i\le$|分值| |:--:|:--:|:--:|:--:| |$1$|$1$|$3\times10^{18}$|$10$| |$2$|$25$|保证 $a_1\le 2\times 10^6$|$10$| |$3$|$10^4$|保证 $a_1\le 2\times 10^6$|$20$| |$4$|$2\times10^6$|$3\times10^{18}$|$60$| 对于 $100\%$ 的数据，$1 \le n \le 2\times10^6$，$1\le a_1<a_2<\dots<a_{n-1}<a_n\le3\times10^{18}$。保证所有输入都是正整数。

Samples

Input #1

2
1 
2

Output #1

-1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[YDOI R1] Running",
    "description": {
      "content": " 小 Z 在一条公路上跑步，公路上有 $n$ 个超市，第 $i$ 个超市的位置为 $a_i$。当小 Z 经过一个超市的时间为奇数时，他就会去逛超市，从而被同学拉爆。 小 Z 最开始位于位置为 $0$ 的点。他会在每个单位时间向右跑 $v$ 个单位长度。 请求出：能够使小 Z 经过 $n$ 个超市中每一个超市时，都不去逛超市的 $v$ 的最大值。 规定 $v$ 必须是正整数，且小 Z 到达",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10183"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 Z 在一条公路上跑步，公路上有 $n$ 个超市，第 $i$ 个超市的位置为 $a_i$。当小 Z 经过一个超市的时间为奇数时，他就会去逛超市，从而被同学拉爆。\n\n小 Z 最开始位于位置为 $0$ 的点。他会在每个单位时间向右跑 $v$ 个单位长度。\n\n请求出：能够使小 Z 经过 $n$ 个超市中每一个超市时，都不去逛超市的 $v$ 的最大值。\n\n规定 $v$ 必须是正整数，且小 Z 到达任意一...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments