hdu5726 rmq+二分

GCD

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 3301 Accepted Submission(s): 1189

Problem Description

Give you a sequence of N(N≤100,000) integers : a1,…,an(0

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =  + ;
ll a[maxn];
ll dp[maxn][];
int Log[maxn];
int n,m;
ll gcd(ll x,ll y)
{
    return x == ?y:gcd(y%x,x);
}
void initRmq()
{
    Log[] = -;
    for(int i = ; i <= n; i++)
    {
        Log[i] = (i&(i - )) == ?Log[i - ] + :Log[i - ];
        dp[i][] = a[i];
    }
    for(int j = ; j <= ; j++)
    {
        for(int i = ; i + (<<j) -  <= n; i++)
        {
            dp[i][j] = gcd(dp[i][j - ],dp[i + (<<(j - ))][j - ]);
        }
    }
}
ll Rmp(int l,int r)
{
    int x = Log[r - l + ];
    return gcd(dp[l][x],dp[r - (<<x) + ][x]);
}
ll bi_search(ll x,int i)
{
    int l = i;
    int r = n;
    int result = l;
    while(l <= r)
    {
        int mid = (l + r)>>;
        ll term = Rmp(i,mid);
        if(term == x)
        {
            l = mid + ;
            result = mid;
        }
        else r = mid - ;;
    }
    return result;
}
int main()
{
    int T;
    scanf("%d",&T);
    int Case = ;
    while(T--)
    {
        map<ll,ll> num;
        scanf("%d",&n);
        for(int i = ; i <= n; i++)
        {
            scanf("%I64d",&a[i]);
        }
        initRmq();
        for(int i = ; i <= n; i++)
        {
            ll x = a[i];
            ll loc = i;
            while(loc <= n)
            {
                ll loc1 = bi_search(x,loc);
                //cout<<loc1<<endl;
                num[x] += loc1 - loc + ;
                loc1++;
                loc = loc1;
                x = gcd(x,a[loc]);
            }
        }
        int l,r;
        scanf("%d",&m);
        printf("Case #%d:\n",Case++);
        for(int i = ; i <= m; i++)
        {
            scanf("%d%d",&l,&r);
            printf("%I64d %I64d\n",Rmp(l,r),num[Rmp(l,r)]);
        }
    }
    return ;
}