Counting Pairs

Posted: 15 Dec, 2020
Difficulty: Moderate


Try Problem

You are given a positive integer N and an equation 1/X + 1/Y = 1/N

You need to determine the count of all possible positive integral solutions (X, Y) for the above equation.


1. X and Y should be greater than 0.
2. (X, Y) and (Y, X) are considered different solutions if X is not equal to Y, i.e. (X, Y) and (Y, X) will not be distinct if X=Y.
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases.

The first and only line of each test case consists of a single positive integer 'N'.
Output Format:
For each test case, print an integer that denotes the count of the number of pairs satisfying the equation in a new line.

The output of each test case should be printed in a separate line.
You don't have to print anything. It has already been taken care of. Just Implement the given function.
1 <= T <= 100
1 <= N <= 10^4

Where 'T' is the number of test cases, and 'N' is the given integer.
Time Limit: 1 sec.
Approach 1
  • Given equation can be simplified as follows:
    • 1/X + 1/Y = 1/N
    • 1/X = 1/N - 1/Y
    • 1/X = (Y - N)/(N*Y)
    • X = (N*Y)/(Y - N)
    • X = (N*Y - N*N + N*N)/(Y-N)
    • X = (N(Y-N) + N*N)/(Y-N)
    • X = N + (N*N)/(Y-N)
  • To identify the total number of pairs satisfying the given equation, iterate over all the possible values of X and Y and increment a counter, where current X and Y values satisfy the above equation.
  • This will give us the count of required pairs.
  • For finding the range of values Y may take, we can see that for an integral solution, N*N should be divisible by Y-N.
    • In the equation, the denominator should be non zero and Y > 0 therefore,
      • Y - N > 0.
      • Y > N.
    • So the smallest positive value that Y may take is N + 1.
    • Also, to get the integral value of X, the denominator should be less than or equal to the numerator, therefore,
      • Y - N <= N*N.
      • Y <= N*N + N.
    • So the highest positive value that Y may take is N*N + N.
  • Similarly, for X, its value also should lie in range (N + 1, N * N + N).
Try Problem