# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Satyam

Tester: Abhinav Sharma, Nishank Suresh

Editorialist: Pratiyush Mishra

# DIFFICULTY:

2157

# PREREQUISITES:

None

# PROBLEM:

You are given an integer N.

You are asked to find total number of integer pairs (A,B) such that

- 1 \leq A,B \leq N
- A^2+B^2+gcd^2(A,B)+lcm^2(A,B)=N. Note that gcd^2(A, B) and lcm^2(A, B) denote the square of gcd and the square of lcm of numbers A and B respectively.

# EXPLANATION:

**GCD Property**: For two numbers A and B, we have:

Here we can loop A from 1 to \lfloor \sqrt{N} \rfloor, and for each value of A we can loop the LCM from A to \lfloor \sqrt{N} \rfloor with increment of A, since LCM would always be a multiple of A. This would cover all the possible values of A and lcm(A,B) and from this we can calculate the value of B as follows:

Now that we got a value of B^2, we first check if its a positive perfect square or not. If not we move to next iteration otherwise we calculate the value of B and check for two conditions:

- lcm(A,B) = LCM
- A^2 + B^2 + gcd^2(A,B) + lcm^2(A,B) = N

If both of these conditions satisfy, this means we found a pair (A,B) that satisfies the above equation. Like this we keep going to calculate the count of all possible pairs that satisfies this equation.

# TIME COMPLEXITY:

O(\sqrt{N}log\sqrt{N}), for each test case.