4467. NOIP-T1-难度

【题目背景】

众所周知小 F 已经出了好几道完全图上的问题了，所以这道也是。

【题目描述】

对 \(n\) 个数 \(a_{1\cdots n}\)，建立一张 \(n\) 个点的完全图 \(G(a_{1\cdots n})\) 如下：

• 点集为 \(V=\{1,2,\cdots,n\}\)
• 边集为 \(E=\{(u,v,w) \,|\, 1\le u<v\le n,\; w=\omega(\text{lcm}(a_u,a_v))\}\)，其中 \(\omega(k)\) 表示 \(k\) 的不同质因子个数，特殊地，\(\omega(1)=0\)
• 换言之，点 \(i,j\) 之间无向边的边权为 \(\text{lcm}(a_i,a_j)\) 的不同质因子个数

现在小 F 会给你 \(q\) 次询问，每次给出 \(l,r\)，请你求出以 \(a_{1\cdots r-l+1}=[l,l+1,\cdots ,r]\) 时得到的图 \(G\) 的最小生成树的边权之和。

【输入格式】

第一行包含一个正整数 \(q\)，表示询问次数。
接下来 \(q\) 行，每行包含两个正整数 \(l,r\)，表示一次询问。

【输出格式】

输出 \(q\) 行，每行包含一个整数表示答案。

【样例输入】

7
2 2
1 9
35 98
114 514
191 9810
12345 56789
888888 1000000

【样例输出】

0
9
137
915
24658
124823
381813

【样例说明】

无

【数据规模与约定】

对所有数据，保证 \(1\le q\le 10^5,1\le l\le r\le 10^6,\sum r\le 2\times 10^6\)。

【来源】

NOIP-T1