HDU - 5726 ​​​​​​​RMQ+二分

GCD

 HDU - 5726 

題目大意：給出了n個數，m次查詢，每次查詢gcd（l,r）并且輸出有多少個區間的gcd==gcd(l,r)；

解題思路：做的時候誤以為要求查詢的區間在（l,r）内，并且也沒有意識到固定左端點移動右端點gcd是單調不增的。

我們可以固定左端點，然後根據上邊那個性質，二分右端點。然後統計貢獻。

#include<bits/stdc++.h>
using namespace std;
#define LL long long

const int N = 1e5+5;
map<int,LL>mmp;
int a[N];
int f[N][20];
void build(int n)
{
    for(int i=1;i<=n;i++)f[i][0]=a[i];

    for(int i=1;i<=19;i++)
    {
        for(int j=1;j+(1<<i)-1<=n;j++)
        {
            f[j][i]=__gcd(f[j][i-1],f[j+(1<<(i-1))][i-1]);
        }
    }
}

int ask(int l,int r)
{
    int k=log2(r-l+1);
    return __gcd(f[l][k],f[r-(1<<k)+1][k]);
}

void solve(int n)
{
    mmp.clear();
    for(int i=1;i<=n;i++)
    {
        int now=f[i][0];
        int L=i,R=i;
        while(L<=n)
        {
            int l=L,r=n;
            int mid;
            while(l<=r)
            {
                int m=(l+r)>>1;
                if(ask(i,m)==now)l=m+1,mid=m;
                else r=m-1;
            }
            mmp[now]+=mid-L+1;
            L=mid+1;
            now=ask(i,L);
        }
    }
}
int main()
{
    int t;
    cin>>t;
    int cas=1;
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        build(n);
        solve(n);
        int m;
        scanf("%d",&m);
        printf("Case #%d:\n",cas++);
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int tmp=ask(x,y);
            printf("%d %lld\n",tmp,mmp[tmp]);
        }
    }
}