Advertisement
OIQ

rayon5

OIQ
Nov 23rd, 2019
212
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <math.h>
  5.  
  6. using namespace std;
  7. vector <int>  t;
  8.  
  9. int gcd(int a, int b) {
  10.     return b ? gcd(b, a % b) : a;
  11. }
  12.  
  13. int get(int v, int l, int r, int L, int R) {
  14.     if (l > R || r < L)
  15.         return 0;
  16.     if (L <= l && R >= r)
  17.         return t[v];
  18.     int d1 = get(2 * v + 1, l, (l + r) / 2, L, R);
  19.     int d2 = get(2 * v + 2, (l + r) / 2 + 1, r, L, R);
  20.  
  21.     return gcd(d1, d2);
  22. }
  23.  
  24.  
  25. int main() {
  26.  
  27.     int n, k;
  28.  
  29.     cin >> n >> k;
  30.  
  31.    
  32.     int N = pow(2, ceil(log2(n)));
  33.    
  34.     t.resize(2 * N - 1, 0);
  35.  
  36.     for (int i = t.size() / 2; i < t.size() / 2 + n; i++)
  37.         cin >> t[i];
  38.  
  39.     for (int i = t.size() / 2 - 1; i > -1; i--)
  40.         t[i] = gcd(t[2 * i + 1], t[2 * i + 2]);
  41.  
  42.     //for (int i = 0; i < t.size(); i++)
  43.         //cout << t[i] << " ";
  44.  
  45.     int ans = 1;
  46.  
  47.  
  48.     for (int i = 0; i < n - k + 1; i++) {
  49.         int c = get(0, t.size() / 2, t.size() - 1, t.size() / 2 + i, t.size() / 2 + i + k - 1);
  50.         ans = max(ans, c);
  51.     }
  52.  
  53.     cout << ans;
  54.  
  55.     return 0;
  56. }
Advertisement
RAW Paste Data Copied
Advertisement