fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1<<19;
  6. const int LOG = 23;
  7.  
  8. int n,a[N],k,g[N][LOG];
  9.  
  10. int gcd(int a, int b) {
  11. 	int r;
  12. 	while(b) r=a%b,a=b,b=r;
  13. 	return a;
  14. }
  15.  
  16. void preprocess() {
  17. 	int i,j;
  18. 	for(i=1;i<=n;i++) g[i][0]=a[i];
  19. 	for(j=1;(1<<j)<=n;j++) for(i=1;i+(1<<j)-1<=n;i++) g[i][j]=gcd(g[i][j-1],g[i+(1<<(j-1))][j-1]);
  20. }
  21.  
  22. int query(int a, int b) {
  23. 	int k=log2(b-a+1);
  24. 	return gcd(g[a][k],g[b-(1<<k)+1][k]);
  25. }
  26.  
  27. bool check(int length) {
  28. 	int i;
  29. 	for(i=1;i+length-1<=n;i++) if(query(i,i+length-1)>=k) return true;
  30. 	return false;
  31. }
  32.  
  33. int main() {
  34. 	int i,left,right,middle;
  35.  
  36. 	scanf("%d %d", &n, &k);
  37. 	for(i=1;i<=n;i++) {
  38. 		scanf("%d", &a[i]);
  39. 	}
  40.  
  41. 	preprocess();
  42.  
  43. 	left=0;
  44. 	right=n+1;
  45. 	while(right-left>1) {
  46. 		middle=(left+right)>>1;
  47. 		if(check(middle)) left=middle;
  48. 		else right=middle;
  49. 	}
  50.  
  51. 	printf("%d\n", left);
  52.  
  53. 	return 0;
  54. }
  55.  
Success #stdin #stdout 0s 52568KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/54qCmX
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!