Advertisement
ivnikkk

Untitled

Dec 24th, 2021
34
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.87 KB | None | 0 0
  1. #include <vector>
  2. #include<iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <iomanip>
  6. #include <fstream>
  7. #include <string>
  8. #include <set>
  9. #include <deque>
  10. #include <queue>
  11. #include <map>
  12. #include <bitset>
  13. #include <random>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. using namespace std;
  18. typedef long long ll;
  19. typedef unsigned long long ull;
  20. typedef long double ld;
  21. #define endl "\n"
  22. #define all(a) a.begin(), a.end()
  23. #define allr(a) a.rbegin(), a.rend()
  24. #define pb push_back
  25. #define F first
  26. #define S second
  27. ll gcd(ll a, ll b) {
  28. while (b != 0) {
  29. ll tmp = a % b;
  30. a = b;
  31. b = tmp;
  32. }
  33. return a;
  34. }
  35. ll get_kek(ll left, ll right, vector<ll>& log, vector <vector<ll>>& sparce) {
  36. ll len = right - left + 1;
  37. ll level = log[len];
  38. return gcd(sparce[level][left], sparce[level][right - (1 << level) + 1]);
  39. }
  40. void solve() {
  41. ll k,n;
  42. cin >> n >> k;
  43. vector<ll> a(n);
  44. for (ll i = 0; i < n; i++) {
  45. cin >> a[i];
  46. }
  47. vector <vector<ll>> sparce(1, vector <ll>(1 + n));
  48. for (ll i = 1; i <= n; i++) {
  49. sparce[0][i] = a[i-1];
  50. }
  51. for (ll len = 1; len * 2 <= n; len *= 2) {
  52. sparce.push_back(sparce.back());
  53. for (ll i = 1; i + len <= n; i++) {
  54. sparce.back()[i] = gcd(sparce.back()[i], sparce.back()[i + len]);
  55. }
  56. }
  57. vector <ll> log(1 + n, 0);
  58. for (ll i = 2; i <= n; i++) log[i] = log[i >> 1] + 1;
  59. ll mx = -1e18;
  60. for (ll i = 0; i <= n - k; i++) {
  61. mx = max(mx, get_kek(i+1, i + k, log, sparce));
  62. }
  63. cout << mx << endl;
  64. }
  65.  
  66. signed main() {
  67. ios_base::sync_with_stdio(false);
  68. cin.tie(nullptr);
  69. ll t = 1;
  70. //cin >> t;
  71. while (t--) {
  72. solve();
  73. }
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement