HDU 5726 GCD (RMQ + 2 점)

GCD
Problem Description
Give you a sequence of
N(N≤100,000) integers :
a1,...,an(0Q(Q≤100,000) queries. For each query
l,r you have to calculate
gcd(al,,al+1,...,ar) and count the number of pairs
(l′,r′)(1≤lgcd(al′,al′+1,...,ar′) equal
gcd(al,al+1,...,ar).

Input
The first line of input contains a number
T, which stands for the number of test cases you need to solve.
The first line of each case contains a number
N, denoting the number of integers.
The second line contains
N integers,
a1,...,an(0The third line contains a number
Q, denoting the number of queries.
For the next
Q lines, i-th line contains two number , stand for the
li,ri, stand for the i-th queries.

Output
For each case, you need to output “Case #:t” at the beginning.(with quotes,
t means the number of the test case, begin from 1).
For each query, you need to output the two numbers in a line. The first number stands for
gcd(al,al+1,...,ar) and the second number stands for the number of pairs
(l′,r′) such that
gcd(al′,al′+1,...,ar′) equal
gcd(al,al+1,...,ar).

Sample Input

 
   
     1 5 1 2 4 6 7 4 1 5 2 4 3 4 4 4

Sample Output

 
   
     Case #1: 1 8 2 4 2 4 6 1 题意：给出一个数列 ，m次询问，每次询问 l，r区间内的gcd值 和 与该区间gcd值相同的区间有多少个 分析： 枚举每一个左端点，找每个左端点对应的所有gcd值区间，预处理出来，由于gcd值呈阶梯下降，所以完全可以处理，此时顺便用map统计区间个数 一开始考虑的是用线段树取gcd值，在加上二分处理，但是发现这样做其实复杂度达到了 n*logn*logn*logn ，直接T掉，然后想到用RMQ O（1）去处理gcd值，降下一个logn成功AC 
    #include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#pragma comment(linker, "/STACK:1024000000,1024000000");

using namespace std;

#define INF 0x3f3f3f3f

int n;
int a[100005];

int dp[100006][30];
int mm[100005];
void initRMQ(int n,int b[])
{
    mm[0]=-1;
    for(int i=1;i<=n;i++)
    {
        mm[i]=(i&(i-1))==0?mm[i-1]+1:mm[i-1];
        dp[i][0]=b[i];
    }
    for(int j=1;j<=mm[n];j++)
        for(int i=1;i+(1<>1;
        int g=rmq(i,mid);
        if(__gcd(g,gcd)>=gcd) l=mid+1;
        else r=mid-1;
    }
    if(__gcd(gcd,rmq(i,l))!=gcd) l--;
    return l;
}

int main()
{
    memset(a,1,sizeof a);
    int T;
    int ca=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
        }
        initRMQ(n,a);
        mapmp;
        for(int i=1; i<=n; i++)
        {
            int gcd=a[i];
            int pos=i;
            while(pos<=n)
            {
                int pos1=Fr(gcd,pos);
                mp[gcd]+=pos1-pos+1;
                pos=pos1+1;
                gcd=__gcd(gcd,a[pos]);
            }
        }
        int m;
        scanf("%d",&m);
        printf("Case #%d:
",ca++);
        while(m--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            int gcd=rmq(a,b);
            printf("%d %lld
",gcd,mp[gcd]);
        }
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU - 1166 - 적병 포진 (나무형 수조 또는 선분 수)

C 국 의 앙 숙 A 국 은 그동안 군사훈련 을 하고 있 었 기 때문에 C 국 간첩 두목 인 데 릭 과 그의 수하 인 티 디 는 또 바 빠 지기 시작 했다.A 국 가 는 해안선 을 따라 직선 으로 N 개 공병 캠프 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU 5726 GCD (RMQ + 2 점)

좋은 웹페이지 즐겨찾기