题目: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<)
ans=(b+)/k-a/k;
else if(a>)
ans=b/k-(a-)/k;
else
ans=b/k-a/k+;
printf("%lld\n",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
**/