1253 : A Simple MST Problem
- 时间限制Time Limit
- 1 秒Sec
- 内存限制Memory Limit
- 256 兆MB
- 提交次数Submitted
- 48 次Times
- 通过次数Solved
- 18 次Times
| 比对Compare | token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored. |
|---|---|
| 不同则错Differs | token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ. |
| 输入Input | 标准输入,格式见题面。Standard input; format as in the statement. |
| 输出Output | 标准输出。Standard output. |
| 时间与内存Time and memory | 记这一份程序的 CPU 时间和内存峰值。题目上的时间限制、内存限制就是这一份的上限。The record is this program’s CPU time and peak memory. The limits on the problem apply to this one run. |
题目描述Description
For the positive integer \(x\), we define the number of its different prime factors as \(\omega(x)\). For example, \(\omega(1)=0,\omega(8)=1,\omega(12)=2\).
In this problem, we treat each positive integer as a node. When we build an edge between node \(x\) and node \(y\), we will cost \(\omega(lcm(x,y))\), where \(lcm(x,y)\) represents the least common multiple of \(x\) and \(y\).
Next, you will be given \(T\) queries. For the \(i\)-th query we will give two integers \(l_i,r_i\). What you need to answer is, when only considering nodes \(l_i,l_i+1,\cdots r_i\), what is the minimum cost if we build edges so that these \(r_i-l_i+1\) nodes can reach each other.
Note that all of the queries are distinct and in \(i\)-th query you can only build an edge between \(x,y\) when \(l_i\le x,y\le r_i\).
输入格式Input
The first line contains an integer \(T(T\le 50000)\) , indicating the number of queries.
For the next \(T\) lines, the \(i\)-th line contains two integers \(l_i,r_i(1\le l_i\le r_i\le 10^6)\), indicating a query.
It is guaranteed that \(\sum_{i=1}^T r_i \le 10^6\).
输出格式Output
For each query, output an integer as your answer.
样例Sample
出题Author
FUDAN