Return to Answer

Python (59 57 56 bytes)

lambda n:0**n+sum((-(n%(x-~x)<1))**x*4for x in range(n))

Online demo

As with my CJam answer, this uses Möbius inversion and runs in pseudoquasilinear time.

Thanks to Sp3000 for 2 bytes' savings, and feersum for 1.

Python (59 57 56 bytes)

lambda n:0**n+sum((-(n%(x-~x)<1))**x*4for x in range(n))

Online demo

As with my CJam answer, this uses Möbius inversion and runs in pseudoquasilinear time.

Thanks to Sp3000 for 2 bytes' savings, and feersum for 1.

Python (59 57 bytes)

lambda n:0**n+4*sum((-(n%(x-~x)<1))**x for x in range(n))

Online demo

As with my CJam answer, this uses Möbius inversion and runs in pseudoquasilinear time.

Thanks to Sp3000 for 2 bytes' savings.

Python (59 57 56 bytes)

lambda n:0**n+sum((-(n%(x-~x)<1))**x*4for x in range(n))

Online demo

As with my CJam answer, this uses Möbius inversion and runs in pseudoquasilinear time.

Thanks to Sp3000 for 2 bytes' savings, and feersum for 1.

Python (59 bytes)

lambda n:(n<1)+4*sum((-(n%(2*x+1)<1))**x for x in range(n))

Online demo

As with my CJam answer, this uses Möbius inversion and runs in pseudoquasilinear time.

Python (59 57 bytes)

lambda n:0**n+4*sum((-(n%(x-~x)<1))**x for x in range(n))

Online demo

As with my CJam answer, this uses Möbius inversion and runs in pseudoquasilinear time.

Thanks to Sp3000 for 2 bytes' savings.