- All Contests
- ProjectEuler+
- Project Euler #192: Best Approximations

# Project Euler #192: Best Approximations

# Project Euler #192: Best Approximations

_{This problem is a programming version of Problem 192 from projecteuler.net}

Let be a real number. A best approximation to for the denominator bound is a rational number in reduced form, with , such that any rational number which is closer to than has a denominator larger than :

For example, the best approximation to for the denominator bound is and the best approximation to for the denominator bound is .

Find the sum of all denominators of the best approximations to for the denominator bound , where is not a perfect square and .

**Input Format**

The only line of each test file contains two integer numbers: and .

**Constraints**

**Output Format**

Print exactly one number which is the answer to the problem modulo

**Sample Input 0**

```
3 10
```

**Sample Output 0**

```
12
```

**Explanation 0**

The best approximation to is . The best approximation to is . .