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)


相关推荐

  • 数模笔记(五):变异系数法

    数模笔记(五):变异系数法数模笔记(一):线性规划、整数规划及非线性规划数模笔记(二):层次分析法数模笔记(三):灰色系统分析方法数模笔记(四):插值与拟合一、原理若某项指标的数值差异较大,能明确区分开各被评价对象,说明该指标的分辨信息丰富,因而应给该指标以较大的权重;反之,若各个被评价对象在某项指标上的数值差异较小,那么这项指标区分各评价对象的能力较弱,因而应给该指标较小的权重。因为方差可以描述取值的离散程度,即某指标的方差反映了该指标的的分辨能力,所以可用方差定义指标的…

  • C语言如何计算数组的长度

    C语言如何计算数组的长度(1)借助sizeof()函数:#include&lt;stdio.h&gt;intmain(){ //定义一个整型数组,并进行初始化赋值9个数据:  intarr[]={1,2,3,4,5,6,7,8,9}; intlength=0; //计算数组中数据长度: //所有数据的字节数除以一个数据的字节数即为数据的个数:  length=sizeof(arr)/…

  • idea全局查找关键字快捷键_hbuilder全局搜索

    idea全局查找关键字快捷键_hbuilder全局搜索简介在使用IDEA时,可以使用双击Shift的方式进行关键字的查找,这是个很好的功能。但IDEA也提供了对于字符串的查找,比如说查找代码中"192.168.1.100"的字符串,又该如何敲击呢。用法Edit-&gt;Find-&gt;FindinPath-&gt;输入感兴趣的内容即可快捷键Ctrl+Shift+F…

    2022年10月24日
  • phpstorm激活码永久[最新免费获取]2022.02.11「建议收藏」

    (phpstorm激活码永久)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html4K…

  • 移动端网页设计_redis client命令

    移动端网页设计_redis client命令一、服务器与客户端的交互Redis服务器是典型的一对多服务器程序:一个服务器可以与多个客户端建立网络连接,每个客户端可以向服务器发送命令请求,而服务器则接收并处理客户端发送的命令请求,并向客户端返回命令回复 Redis服务器通过使用由I/O多路复用技术实现的文件事件处理器,Redis服务器使用单线程单进程的方式来处理命令请求,并与多个客户端进行网络通信clients属性stru…

  • 从char 数据类型到smalldatetime 数据类型的转换导致smalldatetime 值越界

    从char 数据类型到smalldatetime 数据类型的转换导致smalldatetime 值越界
    SQL:
    select*fromdbo.pds_operation_log  where(plan_code=12andcreate_timebetween’1900-01-01’and’2098-12-31′)orderbycreate_time asc
     
    出错:
    消息296,级别16,状态3,第1行
    从char数据类型到smalldatetime数据类型的转换导致smalldatetime值越界。

发表回复

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

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