{"problem":{"name":"[蓝桥杯 2022 国 A] 最大公约数","description":{"content":"给定一个数组，每次操作可以选择数组中任意两个相邻的元素 $x, y$ 并将其中的一个元素替换为 $\\gcd(x, y)$，其中 $\\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数。请问最少需要多少次操作才能让整个数组只含 $1$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8792"},"statements":[{"statement_type":"Markdown","content":"给定一个数组，每次操作可以选择数组中任意两个相邻的元素 $x, y$ 并将其中的一个元素替换为 $\\gcd(x, y)$，其中 $\\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数。请问最少需要多少次操作才能让整个数组只含 $1$。\n\n## Input\n\n输入的第一行包含一个整数 $n$，表示数组长度。\n\n第二行包含 $n$ 个整数 $a_1, a_2,\\dots, a_n$，相邻两个整数之间用一个空格分隔。\n\n## Output\n\n输出一行包含一个整数，表示最少操作次数。如果无论怎么操作都无法满足要求，输出 $-1$。\n\n[samples]\n\n## Note\n\n**【评测用例规模与约定】**\n\n- 对于 $30\\%$ 的评测用例，$n \\leq 500$，$a_i \\leq 1000$；\n- 对于 $50\\%$ 的评测用例，$n \\leq 5000$，$a_i \\leq 10^6$；\n- 对于所有评测用例，$1 \\leq n \\leq 10^5$，$1 \\leq a_i \\leq 10^9$。\n\n蓝桥杯 2022 国赛 A 组 D 题。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8792","tags":["贪心","2022","数论","枚举","蓝桥杯国赛"],"sample_group":[["3\n4 6 9","4"]],"created_at":"2026-03-03 11:09:25"}}