1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. #define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
6. #define dbg(x) cerr << (#x) << " --> " << (x) << endl
7.
8. #define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
9. #define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
10. #define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)
11.
12. #define type(x) __typeof(x.begin())
13.
14. #define orta (bas + son >> 1)
15. #define sag (k + k + 1)
16. #define sol (k + k)
17.
18. #define pb push_back
19. #define mp make_pair
20.
21. #define nd second
22. #define st first
23.
24. #define endl '\n'
25.
26. typedef pair < int ,int > pii;
27.
28. typedef long long ll;
29.
30. const long long linf = 1e18+5;
31. int mod = (int) 1e9 + 7;
32. const int logN = 18;
33. const int inf = 1e9;
34. const int N = 2e5 + 5;
35.
36. int n, m, x, y, z, a[N];
37. vector< int > H[N], v[N];
38. ll sum = 0, ans[N];
39.
40. set< pair< pii , int > > S;
41.
42. void divide(int x) {
43. set< pair< pii , int > > :: iterator it, it2;
44. it = S.lower_bound(mp(mp(x + 1, 0), -1));
45. if(it == S.begin()) return ; it--;
46. if(it->st.nd < x) return ;
47. pair< pii , int > t = *it; S.erase(*it);
48. S.insert(mp(mp(t.st.st, x), t.nd));
49. if(x + 1 <= t.st.nd) S.insert(mp(mp(x + 1, t.st.nd), t.nd));
50. }
51.
52. void remove(int x) {
53. divide(x - 1);
54. while(S.rbegin()->st.st >= x) {
55. pair< pii , int > t = *S.rbegin();
56. sum -= (t.st.nd - t.st.st + 1) * (ll) (t.nd);
57. S.erase(S.find(t));
58. }
59. }
60.
61. void maximize(set< pair< pii , int > > :: iterator it, int x, int y) {
62. pair< pii , int > t; t.nd = x; t.st.st = y;
63. set< pair< pii , int > > :: iterator it2;
64. while(it != S.end()) {
65. if(it->nd >= x) break;
66. t.st.nd = it->st.nd;
67. sum -= (it->st.nd - it->st.st + 1) * (ll) (it->nd);
68. it2 = it; it2++; S.erase(it); it = it2;
69. }
70. if(t.st.st <= t.st.nd) {
71. sum += (t.st.nd - t.st.st + 1) * (ll) t.nd;
72. S.insert(t);
73. }
74. }
75.
76. int main() {
77.
78. scanf("%d", &n);
79.
80. FOR(i, 1, n) {
81. scanf("%d", &a[i]);
82. H[a[i]].pb(i); sum += i;
83. S.insert(mp(mp(i, i), i));
84. }
85.
86. FOR(i, 1, N - 1)
87. for(int j = i; j < N; j += i)
88. foreach(it, H[j])
89. v[i].pb(*it);
90.
91. ans[N - 1] = n * (ll) (n + 1) / 2;
92.
93. ROF(i, N - 2, 1) {
94. int l = v[i].size() - 1;
95. if(l <= 0) { ans[i] = ans[i + 1]; continue; }
96. sort(v[i].begin(), v[i].end()); remove(v[i][1] + 1);
97. maximize(S.begin(), v[i][l-1], 1);
98. divide(v[i][0]); maximize(S.lower_bound(mp(mp(v[i][0] + 1, v[i][0]), 0)), v[i][l], v[i][0] + 1);
99. ans[i] = (S.rbegin()->st.nd * (ll)(n + 1) - sum);
100. }
101.
102. ll all = 0;
103.
104. FOR(i, 1, N - 2) all += (ans[i + 1] - ans[i]) * (ll) i;
105.
106. printf("%lld\n", all);
107.
108. return 0;
109. }
110.
Success #stdin #stdout 0.03s 10496KB
stdin
Standard input is empty
stdout
0