OI Problems   关于

#7hihp7. Ant colony

时间限制:1 s       空间限制:256 MiB       标签: 数据结构 线段树 数学 最大公约数 CodeForces 

算法难度等级:4       思维难度等级:6       实现难度等级:4

本题来源于:Codeforces Round 271 (Div. 2) Problem F


给定长度为 nn 的序列 ss

tt 次询问,每次询问给定 l, rl,\ r,求出对于 lirl\leq i\leq r,存在一个 lkrl\leq k\leq r,使得 sisks_i\nmid s_kii 的个数。

1n, t1051\leq n,\ t\leq 10^51si1091\leq s_i\leq 10^9


Mole is hungry again. He found one ant colony, consisting of nn ants, ordered in a row. Each ant ii ( 1<=i<=n1<=i<=n ) has a strength sis_{i} .

In order to make his dinner more interesting, Mole organizes a version of Hunger Games for the ants. He chooses two numbers ll and rr ( 1<=l<=r<=n1<=l<=r<=n ) and each pair of ants with indices between ll and rr (inclusively) will fight. When two ants ii and jj fight, ant ii gets one battle point only if sis_{i} divides sjs_{j} (also, ant jj gets one battle point only if sjs_{j} divides sis_{i} ).

After all fights have been finished, Mole makes the ranking. An ant ii , with viv_{i} battle points obtained, is going to be freed only if vi=rlv_{i}=r-l , or in other words only if it took a point in every fight it participated. After that, Mole eats the rest of the ants. Note that there can be many ants freed or even none.

In order to choose the best sequence, Mole gives you tt segments [li,ri][l_{i},r_{i}] and asks for each of them how many ants is he going to eat if those ants fight.


The first line contains one integer nn (1≤n≤10^5), the size of the ant colony.

The second line contains nn integers s1,s2,,sns_1,s_2,\ldots,s_n (1≤s_i≤10^9), the strengths of the ants.

The third line contains one integer tt (1≤t≤10^5), the number of test cases.

Each of the next tt lines contains two integers lil_i and rir_i (1≤l_i≤r_i≤n), describing one query.


Print to the standard output tt lines. The ii-th line contains number of ants that Mole eats from the segment [li,ri][l_i,r_i].


1 3 2 4 2
1 5
2 5
3 5
4 5


In the first test battle points for each ant are v=[4,0,2,0,2]v=[4,0,2,0,2], so ant number 11 is freed. Mole eats the ants 2,3,4,52, 3, 4, 5.

In the second test case battle points are v=[0,2,0,2]v=[0,2,0,2], so no ant is freed and all of them are eaten by Mole.

In the third test case battle points are v=[2,0,2]v=[2,0,2], so ants number 33 and 55 are freed. Mole eats only the ant 44.

In the fourth test case battle points are v=[0,1]v=[0,1], so ant number 55 is freed. Mole eats the ant 44.