[Codeforces Round 271 (Div 2) F] [욕심 선분 트 리] Ant colony 구간 은 다른 모든 수인 자의 개수 입 니 다.
4834 단어 욕심데이터 구조-선분 트 리수론 - lcm
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 andr (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 2, 3, 4, 5.
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<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1,class T2>inline void gmax(T1 &a,T2 b){if(b>a)a=b;}
template <class T1,class T2>inline void gmin(T1 &a,T2 b){if(b<a)a=b;}
const int N=0,M=0,Z=1e9+7,ms63=1061109567;
struct A
{
int l,r;
int gcd,minv,num;
}a[1<<18];
int n,m;
int l,r;
int GCD,MINV,NUM;
int gcd(int x,int y)
{
return y==0?x:gcd(y,x%y);
}
void pushup(int o)
{
a[o].gcd=gcd(a[ls].gcd,a[rs].gcd);
a[o].minv=min(a[ls].minv,a[rs].minv);
a[o].num=0;
if(a[o].minv==a[ls].minv)a[o].num+=a[ls].num;
if(a[o].minv==a[rs].minv)a[o].num+=a[rs].num;
}
void build(int o,int l,int r)
{
a[o].l=l;
a[o].r=r;
if(a[o].l==a[o].r)
{
scanf("%d",&a[o].gcd);
a[o].minv=a[o].gcd;
a[o].num=1;
return;
}
int m=(l+r)>>1;
build(ls,l,m);
build(rs,m+1,r);
pushup(o);
}
void get(int o,int l,int r)
{
if(a[o].l==l&&a[o].r==r)
{
if(GCD==-1)GCD=a[o].gcd;
else GCD=gcd(GCD,a[o].gcd);
if(a[o].minv<MINV)
{
MINV=a[o].minv;
NUM=a[o].num;
}
else if(a[o].minv==MINV)
{
NUM+=a[o].num;
}
return;
}
int m=(a[o].l+a[o].r)>>1;
if(r<=m)get(ls,l,r);
else if(l>m)get(rs,l,r);
else
{
get(ls,l,m);
get(rs,m+1,r);
}
}
int main()
{
while(~scanf("%d",&n))
{
build(1,1,n);
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%d%d",&l,&r);
MINV=1e9;NUM=0;GCD=-1;get(1,l,r);
if(GCD%MINV==0)printf("%d
",r-l+1-NUM);
else printf("%d
",r-l+1);
}
}
return 0;
}
/*
【trick&& 】
【 】
n(1e5) 。
[1,1e9] 。
m(1e5) 。
, [l,r] , ,
【 】
【 】
, 。
, , , 。
,
1,
2, , , gcd 。
, ( ), gcd, AC 。
【 && 】
O(mlogn)
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HPU - ACM 여름 훈련 2 주차 14 급 개인전: Problem D [욕심]Problem D Problem Description 그 러 고 보 니 해동 그룹 이 안팎 으로 어려움 을 겪 고 있 고 회사 의 원로 도 XHD 부부 만 남 았 다 고 한다.분명히 여러 해 동안 싸 운 상인 으로서...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.