305630: CF1066A. Vova and Train

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Vova and Train

题意翻译

## 题意描述: $Vova$先生要乘火车去旅行,火车一开始位于$1$点,以每秒1个单位的速度向前行驶,最终到达$L$处。(也就是说,火车在第$1min$时在$1$处,在$2min$时在2处) 铁路沿线挂着一些灯笼,这些灯笼的位于坐标是$v$的倍数的地方,第一个灯笼位于$v$处 同时,有另一列火车停在另一侧的轨道上,这列火车的左右端点位于$l$和$r$处 当$Vova$先生经过一个地点,这个地点既有灯笼,又没有被另一列火车挡住时,我们称$Vova$先生可以看到灯笼,现在,我们需要你求出一路上$Vova$先生能看到几盏灯笼。本题有多组数据。 ## 输入输出格式: ### 输入格式: 第一行:一个整数$t(1≤t≤10^4$),表示数据组数 下面$t$行,每行4个整数$L_i$,$v_i$,$l_i$,$r_i$,$(1≤L,v≤10^9,1≤l≤r≤L)$,各个字母的含义上文已经给出 ### 输出格式: $t$行,每$1$个整数,表示$Vova$先生能看到的灯笼数

题目描述

Vova plans to go to the conference by train. Initially, the train is at the point $ 1 $ and the destination point of the path is the point $ L $ . The speed of the train is $ 1 $ length unit per minute (i.e. at the first minute the train is at the point $ 1 $ , at the second minute — at the point $ 2 $ and so on). There are lanterns on the path. They are placed at the points with coordinates divisible by $ v $ (i.e. the first lantern is at the point $ v $ , the second is at the point $ 2v $ and so on). There is also exactly one standing train which occupies all the points from $ l $ to $ r $ inclusive. Vova can see the lantern at the point $ p $ if $ p $ is divisible by $ v $ and there is no standing train at this position ( $ p \not\in [l; r] $ ). Thus, if the point with the lantern is one of the points covered by the standing train, Vova can't see this lantern. Your problem is to say the number of lanterns Vova will see during the path. Vova plans to go to $ t $ different conferences, so you should answer $ t $ independent queries.

输入输出格式

输入格式


The first line of the input contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of queries. Then $ t $ lines follow. The $ i $ -th line contains four integers $ L_i, v_i, l_i, r_i $ ( $ 1 \le L, v \le 10^9 $ , $ 1 \le l \le r \le L $ ) — destination point of the $ i $ -th path, the period of the lantern appearance and the segment occupied by the standing train.

输出格式


Print $ t $ lines. The $ i $ -th line should contain one integer — the answer for the $ i $ -th query.

输入输出样例

输入样例 #1

4
10 2 3 7
100 51 51 51
1234 1 100 199
1000000000 1 1 1000000000

输出样例 #1

3
0
1134
0

说明

For the first example query, the answer is $ 3 $ . There are lanterns at positions $ 2 $ , $ 4 $ , $ 6 $ , $ 8 $ and $ 10 $ , but Vova didn't see the lanterns at positions $ 4 $ and $ 6 $ because of the standing train. For the second example query, the answer is $ 0 $ because the only lantern is at the point $ 51 $ and there is also a standing train at this point. For the third example query, the answer is $ 1134 $ because there are $ 1234 $ lanterns, but Vova didn't see the lanterns from the position $ 100 $ to the position $ 199 $ inclusive. For the fourth example query, the answer is $ 0 $ because the standing train covers the whole path.

Input

题意翻译

## 题意描述: $Vova$先生要乘火车去旅行,火车一开始位于$1$点,以每秒1个单位的速度向前行驶,最终到达$L$处。(也就是说,火车在第$1min$时在$1$处,在$2min$时在2处) 铁路沿线挂着一些灯笼,这些灯笼的位于坐标是$v$的倍数的地方,第一个灯笼位于$v$处 同时,有另一列火车停在另一侧的轨道上,这列火车的左右端点位于$l$和$r$处 当$Vova$先生经过一个地点,这个地点既有灯笼,又没有被另一列火车挡住时,我们称$Vova$先生可以看到灯笼,现在,我们需要你求出一路上$Vova$先生能看到几盏灯笼。本题有多组数据。 ## 输入输出格式: ### 输入格式: 第一行:一个整数$t(1≤t≤10^4$),表示数据组数 下面$t$行,每行4个整数$L_i$,$v_i$,$l_i$,$r_i$,$(1≤L,v≤10^9,1≤l≤r≤L)$,各个字母的含义上文已经给出 ### 输出格式: $t$行,每$1$个整数,表示$Vova$先生能看到的灯笼数

加入题单

上一题 下一题 算法标签: