{"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 很久很久以前,森林里有一个古老的兔子王国。这个王国里的每只兔子都不可爱,而是非常好斗,所以王国经常处于混乱之中。\u003cbr\u003e 这里有从1到n编号的n只兔子。所有兔子的体重都是整数。由于某种未知的原因,两只兔子只有在它们的体重不互质时才会互相攻击。\u003cbr\u003e 现在国王把这n只兔子按照它们的编号排成一行。国王打算把一些兔子送进监狱。他想知道,如果他把从第i只兔子到第j只兔子(包括第i只和第j只)之间的所有兔子都送进监狱,那么监狱里有多少只兔子不会互相攻击。\u003cbr\u003e 请注意,一只兔子不会攻击自己。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":" 输入包含多个测试用例。\u003cbr\u003e 每个测试用例的第一行包含两个整数n,m,表示兔子的数量和查询次数。\u003cbr\u003e 接下来一行包含n个整数,第i个整数W\u003csub\u003ei\u003c/sub\u003e表示第i只兔子的体重。\u003cbr\u003e 然后是m行。每行代表一个查询。包含两个整数L和R,表示国王想要了解的情况是,如果他把从第L只兔子到第R只兔子都送进监狱。\u003cbr\u003e (1 \u0026lt;\u003d n, m, W\u003csub\u003ei\u003c/sub\u003e \u0026lt;\u003d 200000, 1 \u0026lt;\u003d L \u0026lt;\u003d R \u0026lt;\u003d n)\u003cbr\u003e 输入以n \u003d 0和m \u003d 0结束。\u003cbr\u003e"}},{"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\u003e3 2\r\n2 1 4\r\n1 2\r\n1 3\r\n6 4\r\n3 6 1 2 5 3\r\n1 3\r\n4 6\r\n4 4\r\n2 6\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n1\r\n1\r\n3\r\n1\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"\u003cbr\u003e 在第二个案例中,第4个查询的答案是2,因为只有1和5与区间[2,6]中的其他数字互质。\u003cbr\u003e"}}]}