# Count of pairs of integers up to X and Y that generates equal Quotient and Remainder

Given two integers **X** and **Y**, the task is to count the number of pairs **(m, n)**, such that **m / n = m % n** and** 1 ≤ m ≤ x** and **1 ≤ n ≤ y**.

**Examples:**

Input:X = 4, Y = 5Output:2Explanation:The pairs (3, 2) and (4, 3) satisfy the condition.

Input:X = 3, Y = 1Output :0

**Approach:** The given problem can be solved based on the following observations:

- For the condition to be satisfied, the numerator must be of the form
**(kn + k)**. Therefore,**(kn + k) / n = (kn + k) % n = k.** - It also implies that
**k < n**. Therefore,**k * k < k * n + k <= x.**Hence,**k < sqrt(x)**. - Therefore, iterating from
**1**to**sqrt(x)**for the numerator is sufficient. - Rewriting
**k * n + k ≤ x**gives us**n <= (x / k – 1)**. Also,**n > k**and**n <= y**from the constraints. - For each possible numerator value, count the possible denominator values and update the total count.

Below is the implementation of the above approach.

## C++

`// C++ Program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to calculate the number` `// of pairs satisfying (m / n = m % n)` `void` `countOfPairs(` `int` `x, ` `int` `y)` `{` ` ` `int` `count = 0;` ` ` `// Iterate from 1 to sqrt(x)` ` ` `for` `(` `int` `k = 1; k * k <= x; ++k) {` ` ` `// Combining the conditions -` ` ` `// 1) n > k` ` ` `// 2) n <= y` ` ` `// 3) n <= (x/ k -1)` ` ` `count += max(0, min(y, x / k - 1) - k);` ` ` `}` ` ` `cout << count << ` `"\n"` `;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `x = 4;` ` ` `int` `y = 5;` ` ` `countOfPairs(x, y);` ` ` `return` `0;` `}` |

## Java

`// Java Program for the above approach` `import` `java.io.*;` `class` `GFG {` ` ` `// Function to calculate the number` ` ` `// of pairs satisfying (m / n = m % n)` ` ` `static` `void` `countOfPairs(` `int` `x, ` `int` `y)` ` ` `{` ` ` `int` `count = ` `0` `;` ` ` `// Iterate from 1 to sqrt(x)` ` ` `for` `(` `int` `k = ` `1` `; k * k <= x; ++k) {` ` ` `// Combining the conditions -` ` ` `// 1) n > k` ` ` `// 2) n <= y` ` ` `// 3) n <= (x/ k -1)` ` ` `count` ` ` `+= Math.max(` ` ` `0` `, Math.min(y, x / k - ` `1` `) - k);` ` ` `}` ` ` `System.out.print(count);` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `int` `x = ` `4` `;` ` ` `int` `y = ` `5` `;` ` ` `countOfPairs(x, y);` ` ` `}` `}` |

## Python3

`# python 3 Program for the above approach` `from` `math ` `import` `sqrt` `# Function to calculate the number` `# of pairs satisfying (m / n = m % n)` `def` `countOfPairs(x, y):` ` ` `count ` `=` `0` ` ` `# Iterate from 1 to sqrt(x)` ` ` `for` `k ` `in` `range` `(` `1` `,` `int` `(sqrt(x)) ` `+` `1` `, ` `1` `):` ` ` ` ` `# Combining the conditions -` ` ` `# 1) n > k` ` ` `# 2) n <= y` ` ` `# 3) n <= (x/ k -1)` ` ` `count ` `+` `=` `max` `(` `0` `, ` `min` `(y, x ` `/` `k ` `-` `1` `) ` `-` `k)` ` ` `print` `(` `int` `(count))` `# Driver code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `x ` `=` `4` ` ` `y ` `=` `5` ` ` `countOfPairs(x, y)` ` ` ` ` `# This code is contributed by bgangwar59.` |

## C#

`// C# Program for the above approach` `using` `System;` `public` `class` `GFG {` ` ` `// Function to calculate the number` ` ` `// of pairs satisfying (m / n = m % n)` ` ` `static` `void` `countOfPairs(` `int` `x, ` `int` `y)` ` ` `{` ` ` `int` `count = 0;` ` ` `// Iterate from 1 to sqrt(x)` ` ` `for` `(` `int` `k = 1; k * k <= x; ++k) {` ` ` `// Combining the conditions -` ` ` `// 1) n > k` ` ` `// 2) n <= y` ` ` `// 3) n <= (x/ k -1)` ` ` `count` ` ` `+= Math.Max(` ` ` `0, Math.Min(y, x / k - 1) - k);` ` ` `}` ` ` `Console.Write(count);` ` ` `}` ` ` `// Driver Code` ` ` `static` `public` `void` `Main()` ` ` `{` ` ` `int` `x = 4;` ` ` `int` `y = 5;` ` ` `countOfPairs(x, y);` ` ` `}` `}` |

## Javascript

`<script>` `// JavaScript Program for the above approach` `// Function to calculate the number` `// of pairs satisfying (m / n = m % n)` `function` `countOfPairs(x, y)` `{` ` ` `var` `count = 0;` ` ` `var` `k;` ` ` `// Iterate from 1 to sqrt(x)` ` ` `for` `(k = 1; k * k <= x; ++k) {` ` ` `// Combining the conditions -` ` ` `// 1) n > k` ` ` `// 2) n <= y` ` ` `// 3) n <= (x/ k -1)` ` ` `count += Math.max(0, Math.min(y, x / k - 1) - k);` ` ` `}` ` ` `document.write(count + ` `"<br>"` `);` `}` `// Driver code` ` ` `var` `x = 4;` ` ` `var` `y = 5;` ` ` `countOfPairs(x, y);` `</script>` |

**Output:**

2

**Time Complexity: **O(√X) **Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**