Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include<iostream>
- #include <algorithm>
- #include <cmath>
- #include <iomanip>
- #include <fstream>
- #include <string>
- #include <set>
- #include <deque>
- #include <queue>
- #include <map>
- #include <bitset>
- #include <random>
- #include <cassert>
- #include <unordered_map>
- #include <unordered_set>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- #define endl "\n"
- #define all(a) a.begin(), a.end()
- #define allr(a) a.rbegin(), a.rend()
- #define pb push_back
- #define F first
- #define S second
- ll gcd(ll a, ll b) {
- while (b != 0) {
- ll tmp = a % b;
- a = b;
- b = tmp;
- }
- return a;
- }
- ll get_kek(ll left, ll right, vector<ll>& log, vector <vector<ll>>& sparce) {
- ll len = right - left + 1;
- ll level = log[len];
- return gcd(sparce[level][left], sparce[level][right - (1 << level) + 1]);
- }
- void solve() {
- ll k,n;
- cin >> n >> k;
- vector<ll> a(n);
- for (ll i = 0; i < n; i++) {
- cin >> a[i];
- }
- vector <vector<ll>> sparce(1, vector <ll>(1 + n));
- for (ll i = 1; i <= n; i++) {
- sparce[0][i] = a[i-1];
- }
- for (ll len = 1; len * 2 <= n; len *= 2) {
- sparce.push_back(sparce.back());
- for (ll i = 1; i + len <= n; i++) {
- sparce.back()[i] = gcd(sparce.back()[i], sparce.back()[i + len]);
- }
- }
- vector <ll> log(1 + n, 0);
- for (ll i = 2; i <= n; i++) log[i] = log[i >> 1] + 1;
- ll mx = -1e18;
- for (ll i = 0; i <= n - k; i++) {
- mx = max(mx, get_kek(i+1, i + k, log, sparce));
- }
- cout << mx << endl;
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- ll t = 1;
- //cin >> t;
- while (t--) {
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement