FJNU 1155 Fat Brother’s prediction（胖哥的预言）

Time Limit: 1000MS Memory Limit: 257792K

【Description】

【题目描述】

Fat Brother is a famous prophet, One day he get a prediction that disaster will come after X days. He is too nervous that sudden die. Fortunately he leave a note about number X after he died:

X is a number of integer which can divided exactly by Y range in [L, R]

You want to know what X is.

胖哥是一位大神棍，一天他得到一条预言昭示着大灾变会在X天后降临。结果分分钟就把他给吓死了。好在他死后留有一谶可以解X：

X是[L, R]中可以被Y整除的整数数量

你试图解出X为何。

【Input】

【输入】

There are multiple test cases. The first line of input contains an integer T (T <= 10000) indicating the number of test cases. For each test case:

Contain 3 integer L, R, Y (1 <= L <= R <= 2^63 - 1, 1 <= Y <= 2^63 - 1)

多组测试用例。

第一行是一个整数T(T <= 10000)表示测试用例的数量。对于每个测试用例：

有三个整数L, R, Y (1 <= L <= R <= 2^63 - 1, 1 <= Y <= 2^63 - 1)

【Output】	【输出】
Each case print a number X.	输出每个样例的数字X。

【Sample Input - 输入样例】

【Sample Output - 输出样例】

1 3 2

3 10 3

【Hint】

【提示】

First

case [1, 3] has number [1, 2, 3], only 2 can divided exactly 2. So

answer is 1

Second

case [3, 10] has number [3, 4, 5, 6, 7, 8, 9, 10], number 3, 6, 9 can divided exactly 3, So answer is 3

第一个样例

[1, 3]拥有数字[1, 2, 3]，只有2可以被2整除。所以答案为1

第二个样例

[3, 10]拥有数字[3, 4, 5, 6, 7, 8, 9, 10]，数字3, 6, 9可被3整除，所以答案为3

【题解】

题目要求[L, R]中有几个数能被Y整除

转化一下：求[L, R]中有多少Y的倍数

　　X = [0, R]中Y倍数的个数 - [0, L-1]中Y倍数的个数

　　即X = R/Y – (L-1)/Y

（由于不是数学意义上的乘法，合并后会被余数干扰……作死）

【代码 C++】

 1 #include<cstdio>
 2 int main(){
 3     int t, n;
 4     long long L, R, Y;
 5     while (~scanf("%d", &t)){
 6         while (t--){
 7             scanf("%lld%lld%lld", &L, &R, &Y);
 8             printf("%lld
", R / Y - (L - 1) / Y);
 9         }
10     }
11     return 0;
12 }