How many x can be possible such that a % x = p?

Given two numbers N and P, find out how many numbers X exist such that N % X = P(where % is the remainder of the division of N with X).

Input Format

The only line of input contains two integers N and P separated by single space.


  • 1 <= P < N <= 1000000000

Output Format

Print the only line with the answer.

Sample Input 0

5 1

Sample Output 0


Explanation 0

The values of X are 2 and 4.

5 % 2 = 1 and 5 % 4 = 1.

My approach : iterate from 1 to a-1 and count
is the answer can be like this how many factors(except 1) of number (a-p) have ?
Help me with some good explanation and proof, (if possible).
@l_returns @ashokshaun @aryanc403 :slight_smile:

1 Like

Check all divisors of N-P in O(\sqrt N)

Didnt noticed thats what you wrote in last line.

1 Like

if n%x=p
then (n-p)%x=0
so x is a divisor of n-p
u can easily calculate number of divisors in sqrt(n)

Deal with corner test cases in this approach.

Except 1 na …right?