{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"问题描述","value":{"format":"HTML","content":"\u003csection\u003e\n\n\u003cp\u003eNiwango小朋友养了\\(N\\)只小鸡作为宠物。这些小鸡被编号为从1到\\(N\\),第\\(i\\)只小鸡的尺寸是一个正整数\\(a_i\\)。\u003c/p\u003e\n\u003cp\u003e\\(N\\)只小鸡决定牵着彼此的手(翅膀)形成一些循环。形成循环的方式由\\(1, \\ldots , N\\)的排列\\(p\\)表示。第\\(i\\)只小鸡用它的右手拉住第\\(p_i\\)只小鸡的左手。小鸡们也可以拉住自己的手。\u003c/p\u003e\n\u003cp\u003e我们定义包含第\\(i\\)只小鸡的\u003cem\u003e循环\u003c/em\u003e为由小鸡\\(p_i, p_{p_i}, \\ldots, p_{\\ddots_i} \u003d i\\)组成的集合。可以证明,在每只小鸡拉住其他小鸡的手之后,这\\(N\\)只小鸡可以被分解成循环。\u003c/p\u003e\n\u003cp\u003e一种形成循环的方式的\u003cem\u003e美丽度\u003c/em\u003e \\(f(p)\\) 定义为每个循环中尺寸最小的小鸡的乘积。\n让\\(b_i \\ (1 \\leq i \\leq N)\\)表示在上述过程中形成\\(i\\)个循环的所有可能排列\\(p\\)的\\(f(p)\\)之和。\u003c/p\u003e\n\u003cp\u003e找出\\(b_1, b_2, \\ldots, b_N\\)的最大公约数,并打印它\\({\\rm mod} \\ 998244353\\)。\u003c/p\u003e\n\u003c/section\u003e"}},{"title":"约束条件","value":{"format":"HTML","content":"\u003csection\u003e\n\n\u003cul\u003e\n\u003cli\u003e\\(1 \\leq N \\leq 10^5\\)\u003c/li\u003e\n\u003cli\u003e\\(1 \\leq a_i \\leq 10^9\\)\u003c/li\u003e\n\u003cli\u003e输入中的所有数字均为整数\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/section\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003csection\u003e\n\n\u003cp\u003e输入以以下格式从标准输入给出:\u003c/p\u003e\n\u003cpre\u003e\\(N\\)\r\n\\(a_1\\) \\(a_2\\) \\(\\ldots\\) \\(a_N\\)\r\n\u003c/pre\u003e\n\n\u003c/section\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003csection\u003e\n\n\u003cp\u003e输出答案。\u003c/p\u003e\n\u003c/section\u003e"}},{"title":"示例 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n4 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003csection\u003e\n\n\n\n\u003c/section\u003e\n\n\u003csection\u003e\n\n\n\n\u003cp\u003e在这种情况下,\\(N \u003d 2, a \u003d [ 4, 3 ]\\)。\u003c/p\u003e\n\u003cp\u003e对于排列\\(p \u003d [ 1, 2 ]\\),形成了只有小鸡\\(1\\)的循环和只有小鸡\\(2\\)的循环,因此\\(f([1, 2]) \u003d a_1 \\times a_2 \u003d 12\\)。\u003c/p\u003e\n\u003cp\u003e对于排列\\(p \u003d [ 2, 1 ]\\),形成了两只小鸡\\(1\\)和\\(2\\)的循环,最小的小鸡尺寸是\\(a_2 \u003d 3\\),因此\\(f([2, 1]) \u003d a_2 \u003d 3\\)。\u003c/p\u003e\n\u003cp\u003e现在我们知道\\(b_1 \u003d f([2, 1]) \u003d 3, b_2 \u003d f([1, 2]) \u003d 12\\),\\(b_1\\)和\\(b_2\\)的最大公约数是\\(3\\)。\u003c/p\u003e\n\u003c/section\u003e"}},{"title":"示例 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n2 5 2 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003csection\u003e\n\n\n\n\u003c/section\u003e\n\n\u003csection\u003e\n\n\n\n\u003cp\u003e总是有\\(N!\\)种排列,因为尺寸相同的小鸡可以相互区分。\u003c/p\u003e\n\u003cp\u003e以下图片说明了当\\(p \u003d (2, 1, 4, 3)\\)和\\(p \u003d (3, 4, 1, 2)\\)时形成的循环及其美丽度。\u003c/p\u003e\u003cdiv style\u003d\"text-align: center;\"\u003e\n\u003cimg alt\u003d\"bdd8ce0a7db3b4f920b04551c60aa207.png\" src\u003d\"CDN_BASE_URL/b160bc7b886aa74408baec8d0b1c062b?v\u003d1707033653\"\u003e\n\u003c/div\u003e\u003cp\u003e\u003c/p\u003e\u003c/section\u003e"}}]}