{"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## Input\n\n第一行一个正整数 $n$。\n\n接下来一行为 $n$ 个正整数，其中第 $i$ 个表示 $a_i$。\n\n## Output\n\n如无解，仅输出一行一个整数 $-1$。否则：\n\n第一行输出一个正整数 $x$。\n\n第二行输出一个长度为 $n$ 的 $\\tt 01$ 串，第 $i$ 个数为 $\\tt 0$ 代表 $a_i$ 被划分到集合 $B$ 中，为 $\\tt 1$ 代表 $a_i$ 被划分到集合 $C$ 中。\n\n[samples]\n\n## Background\n\n小 S 共有 $n$ 只可爱的喵喵，第 $i$ 只喵喵有可爱度 $a_i$。小 S 想要把他的喵喵分成两组。考虑到小 S 的喵喵不像某些喵喵有九条命，他的喵喵只有一条，于是一只喵喵不能被同时分到两组内（请不要试图想象这个画面）。同时，如果一只喵喵没有被分到任意一组，他就会十分生气，很有可能导致小 S 失眠。\n\n当然，小 S 也希望两组的**组可爱度**相等。即存在一个正整数 $x$，使得其中一组的 $\\gcd(x, a_i)$ 之和等于另一组的 $\\gcd(x, a_i)$ 之和。请你判断是否可以使得小 S 可以将喵喵分成两组，并可以找出一个 $x$ 使得两组的**组可爱度**相等。\n\n## Note\n\n**本题采用捆绑测试。**\n\n+ Subtask 0（2 pts）：$n$ 为偶数。\n+ Subtask 1（8 pts）：$a_i$ 均为奇数。\n+ Subtask 2（15 pts）：$n \\leq 50$，$a_i \\leq 50$。\n+ Subtask 3（25 pts）：$n \\leq 10^3$，$a_i \\leq 10^3$。\n+ Subtask 4（50 pts）：无特殊限制。\n\n对于所有数据，$1 \\leq n \\leq 10^5$，$1 \\leq a_i \\leq 10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9575","tags":["数学","2023","洛谷原创","Special Judge","O2优化","构造","洛谷月赛","Ad-hoc"],"sample_group":[["3\n1 1 1","-1"],["4\n4 1 2 3","3\n0001\n"]],"created_at":"2026-03-03 11:09:25"}}