qduoj cfenglv的一道简单签到题（区间gcd rmq，二分）

cfenglv的一道简单签到题
发布时间: 2017年6月11日 17:59 最后更新: 2017年6月12日 18:51 时间限制: 4000ms 内存限制: 128M

描述
据说，julyc决定给学弟学妹出一场月赛，于是他脑中浮现了许多很棒棒的出题创意。

而cfenglv恰巧在机房，于是他把一道题的创意说给了cfenglv听：

求区间gcd（最大公约数）大于等于k的最大区间长度len

这个问题cfenglv思考了一下，发现可以做，但是又不想做，于是提议放到月赛上给其他人做，julyc表示同意。

那么，你能把这个这么棒棒的问题给解决吗？

输入
第一行一个整数t代表数据组数
接下来每组数据
第一行输入两个整数n,k
0< n,k<=1e5
接下来n个正整数
保证所有数据不大于1e5

输出
每组数据输出一行，并输出ans

样例输入1 复制
1
5 3
3 6 9 2 5
样例输出1
3

求区间的gcd用rmq，然后二分即可。

#include<stdio.h>
#include<math.h>
#include<map>
using namespace std;
int f[100010][18];
int a[100010];
int n,m;
int Scan()
{
    int res = 0, ch, flag = 0;

    if((ch = getchar()) == '-')             
        flag = 1;

    else if(ch >= '0' && ch <= '9')         
        res = ch - '0';
    while((ch = getchar()) >= '0' && ch <= '9' )
        res = res * 10 + ch - '0';

    return flag ? -res : res;
}


int gcd(int a,int b)
{
  return b?gcd(b,a%b):a;
}
void he()
{
  for(int j=1;j<=n;j++) f[j][0]=a[j];
  for(int i=1;i<18;i++)
  {
    for(int j=1;j<=n;j++)
    {
      if(j+(1<<i)-1 <= n)
      {
        f[j][i]=gcd(f[j][i-1],f[j+(1<<i-1)][i-1]);
      }
    }
  }
}



int look(int i,int j)
{
    int k=0;
    while((1 << (k + 1)) <= j - i + 1) k++;  
    return gcd(f[i][k],f[j-(1<<k)+1][k]);
}


int solve()
{

    int len=0;
  for(int i=1;i<=n;i++)
  {
     int l=i,r=n;
     while(l<=r)
     {
        int mid=(l+r)>>1;
        if(look(i,mid)>=m)
            l=mid+1;
        else r=mid-1;
     }
     len=max(len,r-i+1);
  }
  return len;
}



int main()
{
  int t,l,r;
  int cas=1;
  scanf("%d",&t);
  while(t--)
  {

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
      a[i]=Scan();
    }
    he();
    printf("%d\n",solve() );
  }
  return 0;
}