# Codeforces 474 F. Ant colony

Codeforces 474 F. Ant colony

F. Ant colony
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Mole is hungry again. He found one ant colony, consisting of n ants, ordered in a row. Each ant i (1 ≤ i ≤ n) has a strength si.

In order to make his dinner more interesting, Mole organizes a version of «Hunger Games» for the ants. He chooses two numbers l and r(1 ≤ l ≤ r ≤ n) and each pair of ants with indices between l and r (inclusively) will fight. When two ants i and j fight, ant i gets one battle point only if si divides sj (also, ant j gets one battle point only if sj divides si).

After all fights have been finished, Mole makes the ranking. An ant i, with vi battle points obtained, is going to be freed only if vi = 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 t segments [li, ri] and asks for each of them how many ants is he going to eat if those ants fight.

Input

The first line contains one integer n (1 ≤ n ≤ 105), the size of the ant colony.

The second line contains n integers s1, s2, …, sn (1 ≤ si ≤ 109), the strengths of the ants.

The third line contains one integer t (1 ≤ t ≤ 105), the number of test cases.

Each of the next t lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n), describing one query.

Output

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

Sample test(s)
input
```5
1 3 2 4 2
4
1 5
2 5
3 5
4 5
```

output
```4
4
1
1
```

Note

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

In the second test case battle points are 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], so ants number 3 and 5 are freed. Mole eats only the ant 4.

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

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

const int maxn=100100;
typedef pair<int,int> pII;

pII b[maxn];
int n,s[maxn];
int g[maxn<<2];

int gcd(int x,int y)
{
if(x==0) return y;
return gcd(y%x,x);
}

void build(int l,int r,int rt)
{
if(l==r)
{
g[rt]=s[l];
return ;
}
int mid=(l+r)/2;
build(l,mid,rt<<1); build(mid+1,r,rt<<1|1);
g[rt]=gcd(g[rt<<1],g[rt<<1|1]);
}

int query(int L,int R,int l,int r,int rt)
{
if(r<L||l>R) return 0;
if(L<=l&&r<=R)
{
return g[rt];
}
int mid=(l+r)/2;
int u=query(L,R,l,mid,rt<<1);
int v=query(L,R,mid+1,r,rt<<1|1);
return gcd(u,v);
}

int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",s+i);
b[i]=(make_pair(s[i],i));
}
sort(b+1,b+1+n);
build(1,n,1);
int m;
scanf("%d",&m);
while(m--)
{
int Left,Right;
scanf("%d%d",&Left,&Right);
int G=query(Left,Right,1,n,1);
int from=lower_bound(b+1,b+n+1,make_pair(G,Left))-(b+1);
int to=lower_bound(b+1,b+1+n,make_pair(G,Right+1))-(b+1);
printf("%d\n",(Right-Left+1)-(to-from));
}
return 0;
}
```

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0) ### 相关推荐

• #### 怎么完全卸载赛门铁克_如何干净彻底卸载有密码的诺顿symantec杀毒软件

怎么完全卸载赛门铁克_如何干净彻底卸载有密码的诺顿symantec杀毒软件工具/原料注册表方法/步骤1:点击【开始】菜单，选择【运行】，或直接按【Window徽标键+R】方法/步骤2:输入【smc-stop】后打开程序界面，提示输入密码再打开注册表，按【Window徽标键+R】，然后输入【regedit】敲回车方法/步骤3:依次展开【HKEY_LOCAL_MACHINE\SOFTWARE\Symantec\SymantecEndpointProte…

• #### jsonarray方法_getJSONArray

jsonarray方法_getJSONArray[//JSONArray {“id”:”123″,”courseID”:”huangt-test”,”title”:”提交作业”}, {“content”:null,”beginTime”:1398873600000″endTime”}]//普通对象varperson={name:”bella”,age:18};没…

• #### sql error 904_mysql报2005错误

sql error 904_mysql报2005错误mysql清除relay-log文件方法详解mysql清除relay-log文件方法详解今天在本机的mysql数据目录下发现了许多类似hostname-relay-bin.0000*的文件，该文件一般是在mysqlslave实例上存在。主要用途是记录主从同步的信息，正常情况下会自动删除的。本机未配置过master、slave，…文章白及882016-02-245754浏览量exp导出出现…

排序方法

• #### 数字在排序数组中出现的次数「建议收藏」

数字在排序数组中出现的次数

• #### isnotempty和isnotnull_isannotationpresent()用法

isnotempty和isnotnull_isannotationpresent()用法引入包：org.apache.commons.lang3.StringUtils;1.publicstaticbooleanisEmpty(Stringstr)判断某字符串是否为空，为空的标准是str==null或str.length()==0下面是StringUtils判断是否为空的示例：StringUtils.isEmpty(null)=trueStringUtils.isEm… 