CF474F Ant colony

鼹鼠又饿了。他发现了一个蚂蚁群，共有 $n$ 只蚂蚁，排成一列。每只蚂蚁 $i$（$1 \leq i \leq n$）有一个力量值 $s_i$。 为了让晚饭更有趣，鼹鼠为蚂蚁们组织了一场「饥饿游戏」。他选择两个数字 $l$ 和 $r$（$1 \leq l \leq r \leq n$），所有下标在 $l$ 到 $r$（包括首尾）之间的蚂蚁两两进行对战。当两只蚂蚁 $i$ 和 $j$ 对战时，如果 $s_i$ 能整除 $s_j$，那么蚂蚁 $i$ 获得 1 个战斗点；同理，如果 $s_j$ 能整除 $s_i$，则蚂蚁 $j$ 获得 1 个战斗点。 所有对战结束后，鼹鼠进行排名。对于蚂蚁 $i$，若其获得了 $v_i$ 个战斗点，只有当 $v_i = r-l$ 时，也就是说它参与的每一场对战都得分了，此蚂蚁才能被释放。其余的蚂蚁都将被鼹鼠吃掉。注意，可能存在多只蚂蚁被释放，也可能一只都没有。 为了选择最佳的分段，鼹鼠给出了 $t$ 个区间 $[l_i, r_i]$，询问每个区间内的蚂蚁进行对战后，会有多少只蚂蚁被吃掉。

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示蚂蚁群的数量。 第二行包含 $n$ 个整数 $s_1, s_2, \ldots, s_n$（$1 \leq s_i \leq 10^9$），表示每只蚂蚁的力量值。 第三行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示询问的个数。 接下来的 $t$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），描述一个询问区间。

输出 $t$ 行，第 $i$ 行表示鼹鼠在区间 $[l_i, r_i]$ 吃掉的蚂蚁数量。

在第一个测试样例中，每只蚂蚁的战斗点为 $v = [4, 0, 2, 0, 2]$，所以第 1 只蚂蚁获救。鼹鼠吃掉了第 2、3、4、5 只蚂蚁。 在第二个测试样例中，战斗点为 $v = [0, 2, 0, 2]$，没有蚂蚁被释放，鼹鼠吃掉了全部蚂蚁。 在第三个测试样例中，战斗点为 $v = [2, 0, 2]$，第 3、5 只蚂蚁获救。鼹鼠只吃掉第 4 只蚂蚁。 在第四个测试样例中，战斗点为 $v = [0, 1]$，第 5 只蚂蚁获救。鼹鼠吃掉了第 4 只蚂蚁。 由 ChatGPT 5 翻译