{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e这是一个简单的问题。老师给了Bob一系列关于最大公约数(Greatest Common Divisor,GCD)的问题。在研究了其中一些问题后,Bob觉得GCD很有趣。有一天,他想出了一个关于GCD的新问题。尽管看起来很简单,但Bob自己想不出来。现在他求助于你,问题如下:\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u003cbr\u003e\u0026nbsp;\u0026nbsp;给定一个由 $N$ 个正整数组成的数组 $a$;一个 $a$ 的子数组被定义为 $a_1$ 和 $a_N$ 之间的连续区间。换句话说,$a_i, a_{i+1}, \\cdots, a_{j-1}, a_j$ 是 $a$ 的子数组,对于 $1\\le i\\le j\\le N$。对于形如 $(L, R)$ 的查询,告诉区间 $[L, R]$ 的所有子数组贡献的不同GCD数量。\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"有多个测试用例,一直处理到输入结束。\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u003cbr\u003e\u0026nbsp;\u0026nbsp;对于每个测试用例,第一行包含两个整数 $N$ 和 $Q$,分别表示数组的长度和查询的数量。第二行列出了 $N$ 个正整数,接下来是 $Q$ 行,每行包含两个整数 $L,R$ 用于一个查询。\u003cbr\u003e\u003cbr\u003e你可以假设 \u003cbr\u003e\u0026nbsp;\u0026nbsp;\u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;$1\\le N,Q\\le100000$ \u003cbr\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003cbr\u003e\u0026nbsp;\u0026nbsp; $1\\le a_i\\le1000000$"}},{"title":"输出","value":{"format":"HTML","content":"对于每个查询,在一行中输出答案。"}},{"title":"样例","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\u003e5 3\r\n1 3 4 6 9\r\n3 5\r\n2 5\r\n1 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\r\n6\r\n6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}