「TAOI-2」喵了个喵 Ⅳ

Luogu
IDLGP9575
Time1000ms
Memory512MB
DifficultyP5
数学2023洛谷原创Special JudgeO2优化构造洛谷月赛Ad-hoc
给定正整数 $n$ 及长度为 $n$ 的正整数序列 $a$,请你将 $a$ 划分为两个集合 $B, C$ 并给出正整数 $x$,使得 $\sum_{y\in B}\gcd(x,y) = \sum_{y\in C}\gcd(x,y)$。如果无解,输出 $-1$。 你需要保证 $1 \leq x \leq 10^9$,保证在本题的数据约束下若有解则总有 $x \leq 10^9$ 的解。 ## Input 第一行一个正整数 $n$。 接下来一行为 $n$ 个正整数,其中第 $i$ 个表示 $a_i$。 ## Output 如无解,仅输出一行一个整数 $-1$。否则: 第一行输出一个正整数 $x$。 第二行输出一个长度为 $n$ 的 $\tt 01$ 串,第 $i$ 个数为 $\tt 0$ 代表 $a_i$ 被划分到集合 $B$ 中,为 $\tt 1$ 代表 $a_i$ 被划分到集合 $C$ 中。 [samples] ## Background 小 S 共有 $n$ 只可爱的喵喵,第 $i$ 只喵喵有可爱度 $a_i$。小 S 想要把他的喵喵分成两组。考虑到小 S 的喵喵不像某些喵喵有九条命,他的喵喵只有一条,于是一只喵喵不能被同时分到两组内(请不要试图想象这个画面)。同时,如果一只喵喵没有被分到任意一组,他就会十分生气,很有可能导致小 S 失眠。 当然,小 S 也希望两组的**组可爱度**相等。即存在一个正整数 $x$,使得其中一组的 $\gcd(x, a_i)$ 之和等于另一组的 $\gcd(x, a_i)$ 之和。请你判断是否可以使得小 S 可以将喵喵分成两组,并可以找出一个 $x$ 使得两组的**组可爱度**相等。 ## Note **本题采用捆绑测试。** + Subtask 0(2 pts):$n$ 为偶数。 + Subtask 1(8 pts):$a_i$ 均为奇数。 + Subtask 2(15 pts):$n \leq 50$,$a_i \leq 50$。 + Subtask 3(25 pts):$n \leq 10^3$,$a_i \leq 10^3$。 + Subtask 4(50 pts):无特殊限制。 对于所有数据,$1 \leq n \leq 10^5$,$1 \leq a_i \leq 10^6$。
Samples
Input #1
3
1 1 1
Output #1
-1
Input #2
4
4 1 2 3
Output #2
3
0001
API Response (JSON)
{
  "problem": {
    "name": "「TAOI-2」喵了个喵 Ⅳ",
    "description": {
      "content": "给定正整数 $n$ 及长度为 $n$ 的正整数序列 $a$,请你将 $a$ 划分为两个集合 $B, C$ 并给出正整数 $x$,使得 $\\sum_{y\\in B}\\gcd(x,y) = \\sum_{y\\in C}\\gcd(x,y)$。如果无解,输出 $-1$。 你需要保证 $1 \\leq x \\leq 10^9$,保证在本题的数据约束下若有解则总有 $x \\leq 10^9$ 的解。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9575"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定正整数 $n$ 及长度为 $n$ 的正整数序列 $a$,请你将 $a$ 划分为两个集合 $B, C$ 并给出正整数 $x$,使得 $\\sum_{y\\in B}\\gcd(x,y) = \\sum_{y\\in C}\\gcd(x,y)$。如果无解,输出 $-1$。\n\n你需要保证 $1 \\leq x \\leq 10^9$,保证在本题的数据约束下若有解则总有 $x \\leq 10^9$ 的解。\n\n## I...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments