What's wrong in this c code?

Question

This is a question on Codeforces, link

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.

And below is my source code:

#include <stdio.h>    
#include <stdlib.h>

int count(int k,int a, int b)
{
   if(a>b)
      return 0;

   if(a%k!=0)
      return count(k,a+1,b);

   return 1+count(k,a+1,b);
}

int main()
{
    int k,a,b,counter;
    scanf("%d%d%d",&k,&a,&b);

    if(k==0)
       counter=0;
    else
       counter=count(k,a,b);

    printf("%d",counter);

    return 0;
}

Now, the problem is that when I submit my code ,I get this reply wrong answer at test 57. So, if someone could help me figure out what's wrong.

Answer 1

I would rather use a for loop:

for (int i = a; i < b; ++i) {
    if ((i % k) == 0) {
        printf("%d can be divided by %d\n", i, k);
        ++counter;
    }
}
printf("There are %d numbers divisible by %d between %d and %d\n", counter, k, a, b);

Will output:

-28 can be divided by 7
-21 can be divided by 7
-14 can be divided by 7
-7 can be divided by 7
0 can be divided by 7
7 can be divided by 7
14 can be divided by 7
21 can be divided by 7
28 can be divided by 7
There are 9 numbers divisible by 7 between -30 and 30

If you enter inputs: 7, -30, 30

Answer 2

This is a math problem, really. We have

1 ≤ k ≤ 10¹⁸ < 2⁶⁰
-10¹⁸ ≤ a ≤ b ≤ 10¹⁸

so we need inttypes.h and int64_t to be able to describe a and b; it'll also work for k. To scan the three values, the pattern "%" SCNd64 " %" SCNd64 " %d" SCNd64 "" will work. To print, use pattern "%" PRId64 "". (The inttypes.h header file that contains these was standardized in ISO C99, and is also defined in POSIX.)

The actual problem at hand is to find the number of unique integers n for which

a ≤ n k ≤ b

where a and b are integers, and k is a positive integer. The smallest and largest n fulfill

a ≤ n_min k
b ≥ n_max k

that can be written also as

a ÷ k ≤ n_min
b ÷ k ≥ n_max

where ÷ denotes ordinary division. The number we need to print is the number of unique n, or

n_max - n_min + 1

If we use / for integer division (as done in C, i.e. truncating division), ceil() for ceil (rounding towards positive infinity), and floor() for floor (rounding towards negative infinity), and we remember k is a positive integer, we can write the inequalities as

a ÷ k ≤ ceil( a ÷ k ) = n_min
b ÷ k ≥ floor( b ÷ k ) = n_max

and the number to be printed is

floor( b ÷ k ) - ceil( a ÷ k ) + 1

Although the standard C library provides functions ceil() and floor() in math.h, they only work for floating-point numbers (but even double-precision floating point does not have integer precision over the range -10¹⁸ to +10¹⁸). Instead, we need to use integer rounding "tricks":

ceil( x ÷ k ) = (x + k - 1) / k,   x > 0, k > 0
ceil( x ÷ k ) = x / k,   x ≤ 0, k > 0
 
floor( x ÷ k ) = x / k,   x ≥ 0, k > 0
floor( x ÷ k ) = (x - k + 1) / k,   x < 0, k > 0

The only limitation here is that our integer type must be able to represent numbers from a-k to b+k, inclusive. Since int64_t can represent range (roughly) -9.22×10¹⁸ to +9.22×10¹⁸, we're well covered.

For the actual solution program, you need to scan a, b, k (and I already mentioned the correct patterns for int64_t), verify a ≤ b and k ≥ 1, calculate n_max and n_min using the above math, and finally print the result (again, I mentioned the printf pattern to use for int64_t). It's very straightforward, if you have the math firmly in your grasp.