「点缀光辉的第十四分块」。
首先二离没话说。
然后发现这个贡献貌似有点麻烦。
以下复杂度中均视 \(n,m\) 和值域同阶。
设 \(c(x,[l,r])\) 表示 \(x\) 对 \([l,r]\) 的贡献。
那么根据套路需要计算两种贡献：
第一种，形如 \(c(i,[1,i))\)：
即求出 \([1,i)\) 内 \(a_i\) 的倍数 / 约数个数。
前者可以对于 \(j \in [1,i)\)，枚举 \(a_j\) 的约数累加贡献；
后者可以枚举 \(a_i\) 的约数累加出现次数作为贡献。
第二种，形如 \(c(i,[1,x])\ (i \in [l,r])\)：
即求出 \([1,x]\) 内 \(a_i\) 的倍数 / 约数个数。
前者同样是平凡的，考虑同上处理。
但对于后者，考虑到如此询问有 \(O(n \sqrt n)\) 种，则不能沿用以上做法。
考虑对于 \(j \in [1,x]\)，枚举 \(a_j\) 的倍数累加贡献。但这样在 \(a_j\) 较小时是 \(O(n)\) 的。
那么自然而然想到根号分治，设阈值 \(T\)，当 \(a_j > T\) 时直接如此累加贡献。
否则，实际上可以考虑一个这样的方式：枚举一个不超过 \(T\) 的 \(d\) 计算其贡献，具体地，求出 \([1,x]\) 内 \(d\) 的出现次数乘以 \([l,r]\) 内 \(d\) 的倍数的个数。
注意到后者实际上可以用前缀和处理，而前者仍然是平凡的。
这样算下来时间复杂度是 \(O(n\sqrt n + \frac{n^2}T + nT)\)，空间复杂度是 \(O(nT)\)。
看起来 \(T = \sqrt n\) 就行了，但是这题太紧了，导致空间开不下，而线性空间的处理方式会被卡 cache。
于是 \(T\) 取小一点，我块长取 \(799\)，\(T\) 取 \(150\)，然后就直接过去了完全没卡常（
（当时是因为洛谷评测机变快了 lxl 没发现所以没卡我，不过现在也只要不用 vector 预处理每个数的约数，然后带个 O2 就能过了）
另外，一开始全 WA 差点吓死我，拍了一下发现调试信息没删，删了就过了（
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
w && (x = -x);
}
const int N = 5e5;
const int BLK = 799;
const int LIM = 150;
int n,m,a[N + 5];
int D[(N << 5) + 5],*d[N + 5],c[N + 5];
int block = BLK,pos[N + 5];
int lim = LIM;
long long ans[N + 5];
struct s_query
{
int l,r,id;
long long ans;
inline bool operator<(const s_query &o) const
{
return pos[l] ^ pos[o.l] ? l < o.l : ((pos[l] & 1) ? r < o.r : r > o.r);
}
} qry[N + 5];
struct s_contrib
{
int l,r,id,w;
};
vector<s_contrib> vec[N + 5];
int cnt1[N + 5],cnt2[N + 5],cnt3[N + 5];
int sum1[N + 5],sum2[N + 5];
int cnt[N + 5][LIM + 5];
int main()
{
for(register int i = 1;i <= N;++i)
for(register int j = i;j <= N;j += i)
++c[j];
d[1] = D;
for(register int i = 1;i <= N;++i)
d[i + 1] = d[i] + c[i],c[i] = 0;
for(register int i = 1;i <= N;++i)
for(register int j = i;j <= N;j += i)
d[j][++c[j]] = i;
read(n),read(m);
for(register int i = 1;i <= n;++i)
read(a[i]),pos[i] = (i - 1) / block + 1;
for(register int i = 1;i <= m;++i)
read(qry[i].l),read(qry[i].r),qry[i].id = i;
for(register int i = 1;i <= n;++i)
{
sum1[i] = cnt1[a[i]];
for(register int j = 1;j <= c[a[i]];++j)
sum2[i] += cnt2[d[a[i]][j]],++cnt1[d[a[i]][j]];
for(register int j = 1;j <= lim;++j)
cnt[i][j] = cnt[i - 1][j] + !(a[i] % j);
++cnt2[a[i]];
}
sort(qry + 1,qry + m + 1);
for(register int i = 1,l = 1,r = 0;i <= m;++i)
{
l < qry[i].l && (vec[r].push_back((s_contrib){l,qry[i].l - 1,i,-1}),1);
for(;l < qry[i].l;qry[i].ans += sum1[l] + sum2[l],++l);
l > qry[i].l && (vec[r].push_back((s_contrib){qry[i].l,l - 1,i,1}),1);
for(;l > qry[i].l;qry[i].ans -= sum1[l - 1] + sum2[l - 1],--l);
r < qry[i].r && (vec[l - 1].push_back((s_contrib){r + 1,qry[i].r,i,-1}),1);
for(;r < qry[i].r;qry[i].ans += sum1[r + 1] + sum2[r + 1],++r);
r > qry[i].r && (vec[l - 1].push_back((s_contrib){qry[i].r + 1,r,i,1}),1);
for(;r > qry[i].r;qry[i].ans -= sum1[r] + sum2[r],--r);
}
memset(cnt1,0,sizeof cnt1),memset(cnt2,0,sizeof cnt2);
for(register int i = 1;i <= n;++i)
{
for(register int j = 1;j <= c[a[i]];++j)
++cnt1[d[a[i]][j]];
++cnt2[a[i]];
if(a[i] > lim)
for(register int j = a[i];j <= N;j += a[i])
++cnt3[j];
for(vector<s_contrib>::iterator it = vec[i].begin();it != vec[i].end();++it)
{
for(register int j = it->l;j <= it->r;++j)
qry[it->id].ans += it->w * (cnt1[a[j]] + cnt3[a[j]] - 2 * (j <= i));
for(register int j = 1;j <= lim;++j)
qry[it->id].ans += (long long)it->w * cnt2[j] * (cnt[it->r][j] - cnt[it->l - 1][j]);
}
}
for(register int i = 1;i <= m;++i)
ans[qry[i].id] = (qry[i].ans += qry[i - 1].ans) + qry[i].r - qry[i].l + 1;
for(register int i = 1;i <= m;++i)
printf("%lld\n",ans[i]);
}