因为那时候没怎么补所以就分到了未搞分组里！！！然后因为标题如此之屌吧= =点击量很高，然后写的是无思路，23333，估计看题人真的是觉得博主就是个撒缺。废话不多说了，补题。。。

update////2016/10/3-19：03；

---

题意：

第一个数求给定询问区间的GCD，第二个数求在这个给定区间里面有多少种连续区间的GCD是等于第一个数。

思路：

区间GCD个数可以利用线段树，或者RMQ搞；鉴于RMQ的查询是O(1)，所以RMQ；

求各种GCD的区间数量，预处理掉；

（下面这种说是二分，其实还是很难想到的）

枚举起点，然后其实还是说是枚举终点，只是每次我枚举到一个终点，这个区间是[s,t]，我就可以二分查找到最远的那个区间gcd[i, max_distance]是等于gcd[s,t]，然后后面终点t就会变成最远的那个位置max_distance，以至于可以说是二分终点。

PS:这种二分的写法还是蛮常用的，长见识的把~

#include<map>

#include<cstdio>

#include<iostream>

#include<string.h>

#include<algorithm>

using namespace std;

typedef long long LL;

const int N=1e5+10;

int d[N<<2];

int dp[N][30];

int mm[N];

int a[N];

void RMQ(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<<j)-1<=n;i++)

            dp[i][j]=__gcd(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);

}

int query(int x,int y)

{

    int k=mm[y-x+1];

    return __gcd(dp[x][k],dp[y-(1<<k)+1][k]);

}

map<int ,LL>mp;

int main()

{

    int n,t,q;

    scanf("%d",&t);

    int cas=1;

    while(t--)

    {

        scanf("%d",&n);

        for(int i=1;i<=n;i++)

            scanf("%d",&a[i]);

        RMQ(n,a);

        mp.clear();

        for(int s=1;s<=n;s++)

        {

            int t=s;

            while(t<=n)

            {

                int left=t;

                int right=n;

                int tmp=query(s,left);

                while(left<=right)

                {

                    int mid=(left+right)>>1;

                    if(query(s,mid)==tmp)

                    {

                        left=mid+1;

                    }

                    else

                    {

                        right=mid-1;

                    }

                }

                mp[tmp]+=left-t;

                t=left;

            }

        }

        scanf("%d",&q);

        printf("Case #%d:\n",cas++);

        while(q--)

        {

            int l,r;

            scanf("%d%d",&l,&r);

            int gcd=query(l,r);

            printf("%d %lld\n",gcd,mp[gcd]);

        }

    }

    return 0;

}