剪贴板 y142od3m

```cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int U = 1e6; char *p1, *p2, buf[U]; #define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, U, stdin), p1 == p2) ? EOF : *p1++) int rd() { int s = 0, f = 1; char ch = nc(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = nc(); } while (ch >= '0' && ch <= '9') { s = (s << 3) + (s << 1) + ch - 48; ch = nc(); } return s * f; } void wt(ll x) { if (x < 0) putchar('-'), x = -x; if (x > 9) wt(x / 10); putchar(x % 10 + '0'); } const int N = 1e6 + 10; int B = 55; int n, m, sq; int a[N], mx; int ct; int tp1[N], tp2[N]; ll p[N]; int ct1[N], ct2[N]; int fl1[N], fl2[N]; int s1[N], s2[N]; ll aq[N], cur, ans[N]; vector <int> f[N]; struct query1{ int l, r, id; bool operator < (const query1 &o) const { if (l / sq != o.l / sq) return l < o.l; if (l / sq & 1) return r < o.r; return r > o.r; } }q[N]; struct query2{ int l, r, id, tp, p, rtp; bool operator < (const query2 &o) const { return p < o.p; } }qt[N]; int main() { //freopen("1.in", "r", stdin); //freopen("1.out", "w", stdout); n = rd(), m = rd(); for (int i = 1; i <= n; i++) { a[i] = rd(); mx = max(mx, a[i]); } if (a[1] <= 1000) B = 95; for (int i = 1; i <= m; i++) { int l = rd(), r = rd(); q[i] = {l, r, i}; //ans[i] = r - l + 1; } sq = sqrt(m); sort(q + 1, q + m + 1); int l = 1, r = 0; for (int i = 1; i <= m; i++) { if (r < q[i].r) qt[++ct] = {r + 1, q[i].r, i, 1, l - 1, 0}; if (r > q[i].r) qt[++ct] = {q[i].r + 1, r, i, -1, l - 1, 0}; r = q[i].r; if (l < q[i].l) qt[++ct] = {l, q[i].l - 1, i, 1, r, 0}; if (l > q[i].l) qt[++ct] = {q[i].l, l - 1, i, -1, r, 0}; l = q[i].l; //cout << l << ' '; //cout << i << ' ' << q[i].id << endl; } for (int i = 1; i <= n; i++) { if (!f[a[i]].size()) { for (int j = 1; j * j <= a[i]; j++) { if (!(a[i] % j)) { tp1[j]++; p[i] += tp2[j]; f[a[i]].push_back(j); if (j * j != a[i]) { tp1[a[i] / j]++; p[i] += tp2[a[i] / j]; } } } } else { for (int k = 0; k < f[a[i]].size(); k++) { int j = f[a[i]][k]; tp1[j]++; p[i] += tp2[j]; if (j * j != a[i]) { tp1[a[i] / j]++; p[i] += tp2[a[i] / j]; } } } p[i] += tp1[a[i]], tp2[a[i]]++; //p[i]++; //cout << p[i] << ' '; } //cout << endl; sort(qt + 1, qt + ct + 1); int j = 1; for (int i = 0; i <= n; i++) { if (i) { for (int k = 0; k < f[a[i]].size(); k++) { ct2[f[a[i]][k]]++; if (a[i] / f[a[i]][k] != f[a[i]][k]) ct2[a[i] / f[a[i]][k]]++; } if (a[i] >= B) { for (int k = 1; a[i] * k <= mx; k++) { ct1[a[i] * k]++; } } } while (qt[j].p == i && j <= ct) { ll res = 0; for (int k = qt[j].l; k <= qt[j].r; k++) { res += p[k] + qt[j].rtp - ct1[a[k]] - ct2[a[k]]; //cout << ct1[a[k]] << ' '; } //cout << endl; aq[qt[j].id] += res * qt[j].tp; // cout << qr[j].p << ' ' << qr[j].l << ' ' << qr[j].r << ' '; // cout << qr[j].id << ' ' << res << endl; j++; } } for (int x = 1; x < B; x++) { //if (x > mx) break; //cout << x << endl; for (int i = 1; i <= n; i++) { if (a[i] == x) fl1[i] = 1; else fl1[i] = 0; s1[i] = s1[i - 1] + fl1[i]; } for (int i = 1; i <= n; i++) { if (!(a[i] % x)) fl2[i] = 1; else fl2[i] = 0; s2[i] = s2[i - 1] + fl2[i]; } for (int i = 1; i <= ct; i++) { int l = qt[i].l, r = qt[i].r, p = qt[i].p; ll res = 1ll * s1[p] * (s2[r] - s2[l - 1]); res = -res; aq[qt[i].id] += res * qt[i].tp; //cout << p << ' ' << l << ' ' << r << ' ' << res << endl; } } for (int i = 1; i <= m; i++) { cur += aq[i]; //cout << cur << ' '; ans[q[i].id] += cur; } for (int i = 1; i <= m; i++) { wt(ans[i]); puts(""); } return 0; } ```