[math] Codeforces 597A Divisibility

题目:http://codeforces.com/problemset/problem/597/A

Divisibility

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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 ≤ 1018; - 1018 ≤ a ≤ b ≤ 1018).

Output

Print the required number.

Examples

input

Copy

1 1 10

output

Copy

10

input

Copy

2 -4 4

output

Copy

5

题意:

给一个区间[a,b],问这个区间内有多少个数是k(k>0)的倍数

思路:

首先可以注意到0必定是k的倍数
若用x/k,则得到(0,x](x>0)或[x,0)(x<0)这个区间内有多少个k的倍数,这相当于一个前缀和(注意这里)
所以问[a,b]这个区间有多少个k的倍数时,若a>0且b>0,则ans=b/k-(a-1)/k (a-1是因为a可能是k的倍数,而b/k计算过一遍了,所以从a-1开始算,后面b+1同理),若a<0且b>0,则ans=(b+1)/k-a/k;,否则如果a<=0且b>=0则必定包含了0,所以ans=b/k-a/k+1(这里+1是为了加上0)

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long k,a,b,ans;
    while(cin>>k>>a>>b){
        if(b<0)
            ans=(b+1)/k-a/k;
        else if(a>0)
            ans=b/k-(a-1)/k;
        else
            ans=b/k-a/k+1;
        printf("%lld
",ans);
    }
}
/**
给一个区间[a,b],问这个区间内有多少个数是k(k>0)的倍数
首先可以注意到0必定是k的倍数
若用x/k,则得到(0,x](x>0)或[x,0)(x<0)这个区间内有多少个k的倍数,这相当于一个前缀和(注意这里)
所以问[a,b]这个区间有多少个k的倍数时,若a>0且b>0,则ans=b/k-(a-1)/k (a-1是因为a可能是k的倍数,而b/k计算过一遍了,所以从a-1开始算,后面b+1同理),若a<0且b>0,则ans=(b+1)/k-a/k;,否则如果a<=0且b>=0则必定包含了0,所以ans=b/k-a/k+1(+1是为了加上0)

下面是测试时的一些样例
1 1 10
2 -4 4
1 -1000000000000000000 1000000000000000000
1000000000000000000 -1000000000000000000 1000000000000000000
4 -2 1
4 -3 4
4 0 1
4 -8 -3
4 -8 -4
4 -8 -5
4 5 8
4 7 8
5 1 10
**/