fork(8) download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N = 5e5 + 5;
  4. int n , k;
  5. int arr[N];
  6. int pre[N];
  7. int suf[N];
  8. int gcd(int a , int b){
  9.     while(b){
  10.         int temp = a % b;
  11.         a = b;
  12.         b = temp;
  13.     }
  14.     return a;
  15. }
  16. bool check(int val){
  17.     for(int i = 1 ; i <= n ; i += val){
  18.         int l = i;
  19.         int r = min(n , i + val - 1);
  20.         pre[l] = arr[l];
  21.         for(int j = l + 1 ; j <= r ; ++j){
  22.             pre[j] = gcd(pre[j - 1] , arr[j]);
  23.         }
  24.         suf[r] = arr[r];
  25.         for(int j = r - 1 ; j >= l ; --j){
  26.             suf[j] = gcd(suf[j + 1] , arr[j]);
  27.         }
  28.     }
  29.     for(int i = 1 ; i + val - 1 <= n ; ++i){
  30.         if(gcd(suf[i] , pre[i + val - 1]) >= k){
  31.             return 1;
  32.         }
  33.     }
  34.     return 0;
  35. }
  36. int solve(){
  37.     int l = 1;
  38.     int r = n + 1;
  39.     while(l < r){
  40.         int mid = l + r >> 1;
  41.         if(check(mid)){
  42.             l = mid + 1;
  43.         }
  44.         else{
  45.             r = mid;
  46.         }
  47.     }
  48.     return l - 1;
  49. }
  50. int main(){
  51.     scanf("%d %d" , &n , &k);
  52.     for(int i = 1 ; i <= n ; ++i){
  53.         scanf("%d" , arr + i);
  54.     }
  55.     printf("%d\n" , solve());
  56. }
Success #stdin #stdout 0s 9320KB
comments (?)
stdin
copy 
10 10
10 20 30 35 70 140 175 210 240 270
stdout
copy 
5
https://ideone.com/UKdXBa
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!