在区间找给定值被整除的个数_综合

在区间找给定值被整除的个数

Crawling in process... Crawling failed Time Limit:1000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u

Submit Status

Description

Find the number of k-divisible numbers on the segment [a,?b]. In other words you need to find the number of such integer values x that a?≤?x?≤?b and x is divisible by k.

Input

The only line contains three space-separated integers k, a and b (1?≤?k?≤?10¹⁸;?-?10¹⁸?≤?a?≤?b?≤?10¹⁸).

Output

Print the required number.

Sample Input

Input

1 1 10

Output

Input

2 -4 4

Output

题目大意：给你一个区间【a，b】，再给你一个数k，问在区间【a，b】中能整除k的数的个数。

解题思路：一看区间范围太大了，一般循环扫描肯定超时，不如反向思考下：假设在区间【a，b】中找一个数z，则若需要符合题意，必须a/k=z，z得是整数，那么z的范围就是【b/k，a/k】中的整数的个数。接下来分情况，如果这个新区间包含零，则需要+1，如果这个区间在0的左侧，将其转化成0的右侧，再计算整数个数（否则能wa到死。。。），如果新区间在0的右侧，那么直接计算整数个数。

代码：

#include<stdio.h>
#include<math.h>
int main()
{long long k,a,b;scanf("%lld%lld%lld",&k,&a,&b);if(a<=0&&b>=0){a=a/k;b=b/k;printf("%lld\n",b-a+1);}else{if(b<0){long long tmp=b;b=-a;a=-tmp;}if(a%k==0){printf("%lld\n",b/k-a/k+1);}else{printf("%lld\n",b/k-a/k);}}return 0;
}