fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int mxn = 1e5 + 5;
  5. const int mod = 1e9 + 7;
  6. //
  7. int n, A[mxn];
  8. int ans, st[20][mxn];
  9. //
  10. inline void add (int &a, int b)
  11. {
  12.     a += b;
  13.     if (a >= mod)
  14.         a -= mod;
  15. }
  16. //
  17. void build (void)
  18. {
  19.     for (int i = 1; i <= n; ++i)
  20.         st[0][i] = A[i];
  21.     for (int j = 1; (1 << j) <= n; ++j)
  22.         for (int i = 1; i + (1 << j) - 1 <= n; ++i)
  23.             st[j][i] = __gcd(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
  24. }
  25. int get (int l, int r)
  26. {
  27.     int k = __lg(r - l + 1);
  28.     //
  29.     return __gcd(st[k][l], st[k][r - (1 << k) + 1]);
  30. }
  31. //
  32. int bin_chop (int i, int v)
  33. {
  34.     int l = i, r = n, mid, res;
  35.     //
  36.     while (l <= r)
  37.     {
  38.         mid = l + r >> 1;
  39.         if (get(i, mid) >= v)
  40.             l = mid + 1,
  41.             res = mid;
  42.         else
  43.             r = mid - 1;
  44.     }
  45.     return res;
  46. }
  47. //
  48. void process (void)
  49. {
  50.     cin >> n;
  51.     for (int i = 1; i <= n; ++i)
  52.         cin >> A[i];
  53.  
  54.     build();
  55.     for (int i = 1; i <= n; ++i)
  56.         for (int k, v = A[i], j = i - 1; j < n; j = k, v = get(i, k + 1))
  57.             k = bin_chop(i, v),
  58.             add(ans, 1LL * (k - j) * v % mod);
  59.  
  60.     cout << ans;
  61. }
  62. //
  63. signed main (void)
  64. {
  65.     ios_base::sync_with_stdio(false);
  66.     cin.tie(nullptr), cout.tie(nullptr);
  67.     process();
  68. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oj4PiH
language:
C++14 (gcc 8.3)
created:
3 days 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!