Advertisement
Josif_tepe

Untitled

Mar 27th, 2024
758
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.25 KB | None | 0 0
  1. class Solution{
  2. public:
  3.     vector<int> segment_tree, v;
  4.     int gcd(int a, int b) {
  5.         if(a < b) {
  6.             swap(a, b);
  7.         }
  8.         while(b != 0) {
  9.             int tmp = a % b;
  10.             a = b;
  11.             b = tmp;
  12.         }
  13.         return a;
  14.     }
  15.     void build(int L, int R, int pos) {
  16.         if(L == R) {
  17.             segment_tree[pos] = v[L];
  18.         }
  19.         else {
  20.             int mid = (L + R) / 2;
  21.             build(L, mid, 2 * pos);
  22.             build(mid + 1, R, 2 * pos + 1);
  23.             segment_tree[pos] = gcd(segment_tree[2 * pos], segment_tree[2 * pos + 1]);
  24.         }
  25.     }
  26.     int query(int L, int R, int pos, int i, int j) {
  27.         // L R i L R  j L R
  28.         if(i <= L and R <= j) {
  29.             return segment_tree[pos];
  30.         }
  31.         if(R < i or j < L) {
  32.             return 0;
  33.         }
  34.         int mid = (L + R) / 2;
  35.         return gcd(query(L, mid, 2 * pos, i, j), query(mid + 1, R, 2 * pos + 1, i, j));
  36.     }
  37.     int findSmallestSubArr(int arr[], int n, int g) {
  38.         int ok = -1;
  39.         v.resize(n);
  40.         for(int i = 0; i < n; i++) {
  41.             if(arr[i] == g) {
  42.                 return 1;
  43.             }
  44.             if(arr[i] % g == 0) {
  45.                 ok = 1;
  46.             }
  47.             v[i] = arr[i];
  48.         }
  49.         if(ok == -1) {
  50.             return -1;
  51.         }
  52.         segment_tree.resize(4 * n);
  53.         build(0, n - 1, 1);
  54.         int res = 2e9;
  55.         for(int i = 0; i < n; i++) {
  56.             if(v[i] % g == 0) {
  57.                 int L = i + 1, R = n - 1;
  58.                 int idx = -1;
  59.                 while(L <= R) {
  60.                     int mid = L + (R - L) / 2;
  61.                     int gcd = query(0, n - 1, 1, i, mid);
  62.                     if(gcd == g) {
  63.                         R = mid - 1;
  64.                         idx = mid;
  65.                     }
  66.                     else if(gcd > g) {
  67.                         L = mid + 1;
  68.                     }
  69.                     else {
  70.                         R = mid - 1;
  71.                     }
  72.                 }
  73.                 if(idx != -1) {
  74.                     res = min(res, idx - i + 1);
  75.                 }
  76.             }
  77.         }
  78.         if(res == 2e9) {
  79.             res = -1;
  80.         }
  81.         return res;
  82.     }
  83. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement