rt，被卡飞了，调了半天还是全 TLE 0 pts；代码含义应该是没问题的，但是实在不会卡常，求大佬帮看看，不一定要 AC，能卡到五六十分也很好了，会关注的 qwq

L[],R[] 是二次离线下来的询问；各种 h[],ne[],e[],idx 是邻接表；遍历到 $1\sim i$ 时，buc[x] 表示 $x$ 的出现次数，dcnt[x] 表示 $x$ 在 $1\sim i$ 中有多少个倍数，mcnt[x] 表示 $x$ 在 $1\sim i$ 中有多少个 $>S$（阈值）的因数。

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 5e5 + 5, S = 100; // 值域根号分治的阈值

int n, m, a[N], len, id[N], buc[N], dcnt[N], mcnt[N], pre[N], suf[N], dm[N], ext[N];
int Lh[N], Lne[N], Rh[N], Rne[N], dh[N], dne[15 * N], de[15 * N], Lidx, Ridx, didx;
long long ans[N];
struct Q
{
    int l, r, id;
} q[N];
struct QQ
{
    int l, r, v, id;
} L[N], R[N];

inline void read(int &x)
{
    static char ch = getchar();
    x = 0;
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
}

inline void write(long long x)
{
    if (x > 9)
        write(x / 10);
    putchar(x % 10 ^ 48);
}

inline void dadd(int u, int x) // 因数邻接表的插入函数
{
    de[++didx] = x, dne[didx] = dh[u], dh[u] = didx;
}

inline void Ladd(int u, QQ x) // 从左往右扫描线的邻接表
{
    L[++Lidx] = x, Lne[Lidx] = Lh[u], Lh[u] = Lidx;
}

inline void Radd(int u, QQ x) // 从右往左扫描线的邻接表
{
    R[++Ridx] = x, Rne[Ridx] = Rh[u], Rh[u] = Ridx;
}

int main()
{
    read(n), read(m), len = __builtin_sqrt(n);
    for (int i = 1; i <= n; i++)
        read(a[i]), id[i] = (i + len - 1) / len;
    for (int i = 1; i <= m; i++)
        read(q[i].l), read(q[i].r), q[i].id = i, ext[i] = q[i].r - q[i].l + 1;
    sort(q + 1, q + m + 1, [](Q a, Q b) {
        if (id[a.l] ^ id[b.l])
            return a.l < b.l;
        return id[a.l] & 1 ? a.r < b.r : a.r > b.r;
    }); // 莫队排序
    for (int i = 1, l = 1, r = 0; i <= m; i++) // 莫队二次离线
    {
        if (l < q[i].l)
            Radd(r + 1, {l, q[i].l - 1, 1, q[i].id});
        if (l > q[i].l)
            Radd(r + 1, {q[i].l, l - 1, -1, q[i].id});
        l = q[i].l;
        if (r > q[i].r)
            Ladd(l - 1, {q[i].r + 1, r, 1, q[i].id});
        if (r < q[i].r)
            Ladd(l - 1, {r + 1, q[i].r, -1, q[i].id});
        r = q[i].r;
    }
    for (int i = 1; i < N; i++) // 预处理所有数的因数
        for (int j = i; j < N; j += i)
            dadd(j, i);
    for (int i = 1; i <= n; i++)
    {
        for (int p = dh[a[i]]; p; p = dne[p]) // 遍历因数
            dcnt[de[p]]++;
        buc[a[i]]++, pre[i] = dcnt[a[i + 1]];
        for (int p = dh[a[i + 1]]; p; p = dne[p])
            pre[i] += buc[de[p]];
        if (a[i] > S)
            for (int j = a[i]; j < N; j += a[i])
                mcnt[j]++;
        for (int p = Lh[i]; p; p = Lne[p])
            for (int j = L[p].l; j <= L[p].r; j++)
                ans[L[p].id] += L[p].v * (dcnt[a[j]] + mcnt[a[j]]);
    }
    memset(buc, 0, sizeof buc), memset(dcnt, 0, sizeof dcnt), memset(mcnt, 0, sizeof mcnt);
    for (int i = n; i; i--)
    {
        for (int p = dh[a[i]]; p; p = dne[p])
            dcnt[de[p]]++;
        buc[a[i]]++, suf[i] = dcnt[a[i - 1]];
        for (int p = dh[a[i - 1]]; p; p = dne[p])
            suf[i] += buc[de[p]];
        if (a[i] > S)
            for (int j = a[i]; j < N; j += a[i])
                mcnt[j]++;
        for (int p = Rh[i]; p; p = Rne[p])
            for (int j = R[p].l; j <= R[p].r; j++)
                ans[R[p].id] += R[p].v * (dcnt[a[j]] + mcnt[a[j]]);
    }
    for (int x = 1; x <= S; x++)
    {
        memset(dm, 0, sizeof dm);
        for (int i = 1; i <= n; i++)
            dm[i] = dm[i - 1] + (a[i] % x == 0);
        for (int i = 1, cnt = 0; i <= n; i++)
        {
            cnt += a[i] == x;
            for (int p = Lh[i]; p; p = Lne[p])
                ans[L[p].id] += L[p].v * cnt * (dm[L[p].r] - dm[L[p].l - 1]);
        }
        for (int i = n, cnt = 0; i; i--)
        {
            cnt += a[i] == x;
            for (int p = Rh[i]; p; p = Rne[p])
                ans[R[p].id] += R[p].v * cnt * (dm[R[p].r] - dm[R[p].l - 1]);
        }
    }
    for (int i = 1, l = 1, r = 0; i <= m; i++) // 处理没有预处理的贡献
    {
        auto &v = ans[q[i].id] += ans[q[i - 1].id];
        while (l > q[i].l)
            v += suf[l--];
        while (l < q[i].l)
            v -= suf[++l];
        while (r < q[i].r)
            v += pre[r++];
        while (r > q[i].r)
            v -= pre[--r];
    }
    for (int i = 1; i <= m; i++)
        write(ans[i] + ext[i]), putchar('\n'); // 最后加上每个数和自己的贡献
    return 0;
}