My code gives time limit exceeded can any one have optimized way

Question

You are given an integer NN.

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

1≤A,B≤N1≤A,B≤N

A2+B2+gcd2(A,B)+lcm2(A,B)=NA2+B2+gcd2(A,B)+lcm2(A,B)=N. Note that gcd2(A,B)gcd2(A,B) and lcm2(A,B)lcm2(A,B) denote the square of gcd and the square of lcm of numbers AA and BB respectively.

Input Format

The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.

The only line of each test case contains an integer NN.

Output Format

For each test case, output in a single line, number of valid pairs (A,B)(A,B).

Constraints

1≤T≤1051≤T≤105

4≤N≤10104≤N≤1010

Sum of NN over all test cases does not exceed 10101010.

Sample Input 1 

3 4 10 20

Sample Output 1 

1 2 2

Explanation

Test case 1: The only valid pair is (1,1)(1,1). Here:

1≤1≤41≤1≤4.

12+12+gcd2(1,1)+lcm2(1,1)=1+1+1+1=412+12+gcd2(1,1)+lcm2(1,1)=1+1+1+1=4.

Test case 2: Only 22 pairs are possible. These are: (1,2)(1,2) and (2,1)(2,1).

https://code.sololearn

Answer 1

https://code.sololearn.com/c56yqB52JAb4/?ref=app

Answer 2

This is my code

Answer 3

Please help

Answer 4

Can you reduce the long long types to use a shorter, faster type, like int? That change alone might cut the time in half.

You can remove the overhead of calling the pow function. Since you are only squaring the integers, then simply multiply the integer to itself. Use i*i instead of pow(i,2). In the case of pow(__gcd(i,j),2) avoid calling gcd twice [i.e., __gcd(i,j)*__gcd(i,j) --> no no!] by assigning the result of gcd to a variable first. Then square the variable. [yes: tmp = __gcd(i,j); then tmp*tmp].

Beware that if you reduce to int types, then it might start using your own gcd function, which is implemented recursively (that means slow :). You should remove that function to ensure the library version gets called.

Answer 5

Gcd function is used to find lcm

Answer 6

Now also give tle

Answer 7

The original posted code is not calling the gcd function that is defined therein. You may as well remove that definition. Instead, the code is calling the library gcd, which is certainly faster, anyway.

Still getting TLE after all the changes? There are some tweaks that could help further, but I expect the compiler optimizer should be doing those already, such as removing loop invariants and unnecessary repeated calculations. Maybe there is a better algorithm. I don't know if it is possible in this case, but sometimes loops can be replaced with higher math.