qduoj cfenglv的一道简单签到题(区间gcd rmq,二分)

xiaoxiao2021-02-28  11

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; }
转载请注明原文地址: https://www.6miu.com/read-200138.html

最新回复(0)