fork download
copy 
  1. // Author: _Sherbiny
  2.  
  3. #include "bits/stdc++.h"
  4.  
  5. using namespace std;
  6. typedef long long ll;
  7. #define endl '\n'
  8.  
  9. void file() {
  10. #ifndef ONLINE_JUDGE
  11.     freopen("in.in", "r", stdin);
  12.     freopen("o.in", "w", stdout);
  13. #endif
  14. }
  15.  
  16. #define Hi ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); file();
  17. /////////////////////////////////////////////////////////////////////////////
  18.  
  19. template<class T>
  20. struct SparseTable {
  21.     // change mxLog
  22.     static const int mxLog = 21;
  23.     vector<array<T, mxLog>> table;
  24.     vector<int> lg;
  25.     int n;
  26.  
  27.     SparseTable(int sz) {
  28.         n = sz;
  29.         table.resize(n + 1);
  30.         lg.resize(n + 1);
  31.         for (int i = 0; i <= n; ++i) lg[i] = __lg(i);
  32.     }
  33.  
  34.     void build(vector<T> &v) {
  35.         for (int i = 0; i < v.size(); ++i) table[i][0] = v[i];
  36.         for (int j = 1; j < mxLog; ++j)
  37.             for (int i = 0; i + (1 << j) - 1 < n; ++i)
  38.                 table[i][j] = merge(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
  39.     }
  40.  
  41.     T merge(T &l, T &r) {
  42.         return max(l, r);
  43.     }
  44.  
  45.     T query(int l, int r) {
  46.         int j = lg[r - l + 1];
  47.         return merge(table[l][j], table[r - (1 << j) + 1][j]);
  48.     }
  49. };
  50.  
  51. const int N = 5e5 + 10, mod = 1e9 + 7;
  52. SparseTable<pair<int, int>> sp(N);
  53. vector<int> divs[N];
  54. int dp[N];
  55.  
  56. void go(int l, int r) {
  57.     if (l > r) return;
  58.     auto [mx, mid] = sp.query(l - 1, r - 1);
  59.  
  60.     if (mid - l < r - mid) {
  61.         for (int i = l; i <= mid; ++i) {
  62.             for (int &d: divs[i]) {
  63.                 int cnt = r / d - (mid - 1) / d;
  64.                 dp[d] += 1ll * cnt * mx % mod;
  65.                 if (dp[d] >= mod) dp[d] -= mod;
  66.             }
  67.         }
  68.     } else {
  69.         for (int i = mid; i <= r; ++i) {
  70.             for (int &d: divs[i]) {
  71.                 int cnt = mid / d - (l - 1) / d;
  72.                 dp[d] += 1ll * cnt * mx % mod;
  73.                 if (dp[d] >= mod) dp[d] -= mod;
  74.             }
  75.         }
  76.     }
  77.  
  78.     go(l, mid - 1), go(mid + 1, r);
  79. }
  80.  
  81. void magic(int tc = 0) {
  82.     int n;
  83.     cin >> n;
  84.     vector<pair<int, int>> v(n);
  85.     for (int i = 0; i < n; ++i)
  86.         cin >> v[i].first, v[i].second = i + 1;
  87.  
  88.     for (int i = 1; i < N; ++i)
  89.         for (int j = i; j < N; j += i)
  90.             divs[j].push_back(i);
  91.  
  92.     sp.build(v);
  93.  
  94.     go(1, n);
  95.  
  96.     int res = 0;
  97.     for (int i = N - 1; i; --i) {
  98.         for (int j = i * 2; j < N; j += i) {
  99.             dp[i] -= dp[j];
  100.             if (dp[i] < 0) dp[i] += mod;
  101.         }
  102.  
  103.         res += 1ll * dp[i] * i % mod * i % mod;
  104.         if (res >= mod) res -= mod;
  105.     }
  106.  
  107.     cout << res << endl;
  108. }
  109.  
  110. signed main() {
  111.     Hi
  112.     int tc = 1;
  113.     while (tc--)
  114.         magic(tc);
  115. }
Success #stdin #stdout 0.67s 144040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/oMf0c9
language:
C++ (gcc 8.3)
created:
111 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!