{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"给你一个 $n$ 个数的序列 $a_i$ ,和 $q$ 次询问,每次询问一段区间 $[l,r]$,问至少要把这个区间分为几个子区间,才能使得每个子区间内的数的乘积等于这个子区间内所有数的 LCM(最小公倍数) 。\n\n$n,a_i,q\\le 10^5$"}},{"title":"Input","value":{"format":"HTML","content":"第一行有两个数字 ,$n,q$($1\\le n,q \\le 10^5 $)\u003cbr\u003e\n第二行$n$个数字,$a_1,a_2,\\dotsm,a_n(1\\leq a_i \\leq 10^5)$\u003cbr\u003e\n接下来有 $q$ 行,每行包含两个数字 $l,r(1\\leq l \\leq r \\leq n)$,表示区间"}},{"title":"Output","value":{"format":"HTML","content":"对于每个答案,打印题目所求答案"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e6 3\n2 3 10 7 5 14\n1 6\n2 4\n3 5\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e3\n1\n2\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"第一个询问包含了整个数组。你可以把它们分成 $$$[2]$$$, $$$[3,10,7]$$$,$$$[5,14]$$$. \u003cbr\u003e第一个子段的乘积和LCM都等于 $$$2$$$. 第二个子段的乘积和LCM都等于$$$210$$$. 第三个子段的乘积和LCM都等于 $$$70$$$\u003cbr\u003e另一个合法的分法是 $$$[2,3]$$$, $$$[10,7]$$$, and $$$[5,14]$$$.\u003c/p\u003e\n\u003cp\u003e第二个询问的范围是 $$$(2,4)$$$. 它的乘积和LCM是相等的,你不用切割这个区间\u003cbr\u003e\n\u003cp\u003e最后一个询问的范围是 $$$(3,5)$$$. 你可以把它分成 $$$[10,7]$$$,$$$[5]$$$.\u003c/p\u003e"}}]}