Codeforces 474 F. Ant colony

Codeforces 474 F. Ant colony

大家好,又见面了,我是全栈君。

线段树求某一段的GCD…..

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;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116374.html原文链接:https://javaforall.cn

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

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

(0)


相关推荐

  • vmware10.0密钥_windows10永久激活密钥

    vmware10.0密钥_windows10永久激活密钥VMwareWorkstation是功能最强大的热门虚拟机软件,现已自带原生简体中文。用户可在在虚拟机同时运行各种操作系统,进行开发、测试、演示和部署软件,虚拟机中复制服务器、台式机和平板环境,每个虚拟机可分配多个处理器核心、千兆字节的主内存和显存。VMwareWorkstation™11延续了VMware的传统,即提供技术专业人员每天在使用虚拟机时所依赖的领先功能和性能。借

  • 查看linux上面是否有安装redis,redis开机启动

    1、检测是否有安装redis-cli和redis-server;[root@localhostbin]#whereisredis-cliredis-cli:/usr/bin/redis-cli[root@localhostbin]#whereisredis-serverredis-server:/usr/bin/redis-server说明已经安装好了,如果不知道怎么安装,告诉

  • 贪吃蛇–[纯C实现]–[一步一步的讲解]–【有音乐】

    贪吃蛇–[纯C实现]–[一步一步的讲解]–【有音乐】目录一、游戏说明1.1游戏按键说明1.2计分系统二、游戏运行2.1游戏效果展示2.2一个报错的纠正2.3游戏代码三、游戏框架构建3.1游戏界面的大小3.2蛇头和蛇身3.2.1蛇头3.2.2蛇身3.3标记游戏区3.3.1存储游戏区的各个位置是什么3.3.2用宏来使某些数字具有特殊意义3.4菜单栏的设置四.隐藏光标的设置4.1光标信息的结构体成员4.2隐藏光标的实现4.3GetStdHandle函数使用介绍4.4…

  • ZOJ1586

    ZOJ1586

  • Python 读取txt文件

    Python 读取txt文件1.首先将数据加载到Python中,看需要做哪些处理。2、从显示的内容可以看出,两个数字之间是以空格,作为分隔符,这里读成一行了。使用sep=””处理,打印查看效果。3、使用分隔符后,分成了三列。但是还有一个问题,第一行被当成了表头,解决方法:使用names=[]给每列命名~ok啦,现在可以实现读取txt文件的任务了~…

  • 安卓中activity的生命周期_产品生命周期五个阶段

    安卓中activity的生命周期_产品生命周期五个阶段Android系统根据生命周期的不同阶段唤起对应的回调函数来执行代码。系统存在启动与销毁一个activity的一套有序的回调函数。本节来讨论下不同生命周期的回调函数里都该做哪些事情,不该做哪些事情。理解生命周期的回调在一个activity的生命周期中,系统会像金字塔模型一样去调用一系列的生命周期回调函数。Activity生命周期的每一个阶段就像金字塔中的台阶。当系统创建了一个新的activity实例

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号