fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5. const int N = 3e5 + 7;
  6. const int lg = 19;
  7. int a[N], l[N], r[N], st[N][lg];
  8. deque<int> dq;
  9. void init(int n) {
  10.     for (int i = 1; i <= n; i++) {
  11.         st[i][0] = a[i];
  12.     }
  13.     for (int j = 1; j < lg; j++) {
  14.         for (int i = 1; i + (1 << j) - 1 <= n; i++) {
  15.             st[i][j] = __gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  16.         }
  17.     }
  18.     for (int i = 1; i <= n; i++) {
  19.         while (!dq.empty() && a[dq.back()] > a[i]) dq.pop_back();
  20.         l[i] = dq.empty() ? 1 : dq.back() + 1;
  21.         dq.push_back(i);
  22.     }
  23.     dq.clear();
  24.     for (int i = n; i >= 1; i--) {
  25.         while (!dq.empty() && a[dq.back()] > a[i]) dq.pop_back();
  26.         r[i] = dq.empty() ? n : dq.back() - 1;
  27.         dq.push_back(i);
  28.     }
  29. }
  30. int get(int x, int y) {
  31.     int k = __lg(y - x + 1);
  32.     return __gcd(st[x][k], st[y - (1 << k) + 1][k]);
  33. }
  34. signed main() {
  35.     ios_base::sync_with_stdio(0);
  36.     cin.tie(0); cout.tie(0);
  37.  
  38.     int n; cin >> n;
  39.     for (int i = 1; i <= n; i++) {
  40.         cin >> a[i];
  41.     }
  42.     init(n);
  43.     ll ans = 0;
  44.     for (int i = 1; i <= n; i++) {
  45.         int len1 = 0, len2 = 0;
  46.         int st = l[i], en = i;
  47.         while (st <= en) {
  48.             int mid = (st + en) >> 1;
  49.             if (get(mid, i) == a[i]) {
  50.                 len1 = i - mid + 1;
  51.                 en = mid - 1;
  52.             }else st = mid + 1;
  53.         }
  54.         st = i, en = r[i];
  55.         while (st <= en) {
  56.             int mid = (st + en) >> 1;
  57.             if (get(i, mid) == a[i]) {
  58.                 len2 = mid - i + 1;
  59.                 st = mid + 1;
  60.             }else en = mid - 1;
  61.         }
  62.         ans += 1LL * len1 * len2 - 1;
  63.     }
  64.     cout << ans << '\n';
  65.     return 0;
  66. }
Success #stdin #stdout 0.01s 10204KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/SkZ83k
language:
C++ (gcc 8.3)
created:
18 hours ago
visibility:
public

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!