Problem 556
Squarefree Gaussian Integers
A Gaussian integer is a number z = a + bi where a, b are integers and i2 = -1.
Gaussian integers are a subset of the complex numbers, and the integers are the subset of Gaussian integers for which b = 0.
A Gaussian integer unit is one for which a2 + b2 = 1, i.e. one of 1, i, -1, -i.
Let’s define a proper Gaussian integer as one for which a > 0 and b ≥ 0.
A Gaussian integer z1 = a1 + b1i is said to be divisible by z2 = a2 + b2i if z3 = a3 + b3i = z1/z2 is a Gaussian integer.
$$\frac {z_1} {z_2} = \frac {a_1 + b_1 i} {a_2 + b_2 i} = \frac {(a_1 + b_1 i)(a_2 - b_2 i)} {(a_2 + b_2 i)(a_2 - b_2 i)} = \frac {a_1 a_2 + b_1 b_2} {a_2^2 + b_2^2} + \frac {a_2 b_1 - a_1 b_2} {a_2^2 + b_2^2}i = a_3 + b_3 i$$
So, z1 is divisible by z2 if $\frac {a_1 a_2 + b_1 b_2} {a_2^2 + b_2^2}$ and $\frac {a_2 b_1 - a_1 b_2} {a_2^2 + b_2^2}$ are integers.
For example, 2 is divisible by 1 + i because 2/(1 + i) = 1 - i is a Gaussian integer.
A Gaussian prime is a Gaussian integer that is divisible only by a unit, itself or itself times a unit.
For example, 1 + 2i is a Gaussian prime, because it is only divisible by 1, i, -1, -i, 1 + 2i, i(1 + 2i) = i - 2, -(1 + 2i) = -1 - 2i and -i(1 + 2i) = 2 - i.
2 is not a Gaussian prime as it is divisible by 1 + i.
A Gaussian integer can be uniquely factored as the product of a unit and proper Gaussian primes.
For example 2 = -i(1 + i)2 and 1 + 3i = (1 + i)(2 + i).
A Gaussian integer is said to be squarefree if its prime factorization does not contain repeated proper Gaussian primes.
So 2 is not squarefree over the Gaussian integers, but 1 + 3i is.
Units and Gaussian primes are squarefree by definition.
Let f(n) be the count of proper squarefree Gaussian integers with a2 + b2 ≤ n.
For example f(10) = 7 because 1, 1 + i, 1 + 2i, 1 + 3i = (1 + i)(2 + i), 2 + i, 3 and 3 + i = -i(1 + i)(1 + 2i) are squarefree, while 2 = -i(1 + i)2 and 2 + 2i = -i(1 + i)3 are not.
You are given f(102) = 54, f(104) = 5218 and f(108) = 52126906.
Find f(1014).
无平方因子的高斯整数
高斯整数是指形如z = a + bi的数，其中a, b均为整数，i2 = -1。
高斯整数是复数的一个子集，而一般意义上的整数又是高斯整数取b = 0的一个子集。
高斯整数的单位满足a2 + b2 = 1，这样的数包括1, i, -1, -i。
我们定义真高斯整数为满足a > 0且b ≥ 0的高斯整数。
如果z3 = a3 + b3i = z1/z2仍然是高斯整数，我们就称高斯整数z1 = a1 + b1i能够被z2 = a2 + b2i整除。
$$\frac {z_1} {z_2} = \frac {a_1 + b_1 i} {a_2 + b_2 i} = \frac {(a_1 + b_1 i)(a_2 - b_2 i)} {(a_2 + b_2 i)(a_2 - b_2 i)} = \frac {a_1 a_2 + b_1 b_2} {a_2^2 + b_2^2} + \frac {a_2 b_1 - a_1 b_2} {a_2^2 + b_2^2}i = a_3 + b_3 i$$
因此，z1被z2整除当且仅当$\frac {a_1 a_2 + b_1 b_2} {a_2^2 + b_2^2}$和$\frac {a_2 b_1 - a_1 b_2} {a_2^2 + b_2^2}$都是整数。
例如，2被1 + i整除，因为2/(1 + i) = 1 - i是高斯整数。
高斯素数是指只能被单位、其本身或其本身乘以单位所整除的高斯整数。
例如，1 + 2i是高斯素数，因为它只能被1, i, -1, -i, 1 + 2i, i(1 + 2i) = i - 2, -(1 + 2i) = -1 - 2i和-i(1 + 2i) = 2 - i整除。
2不是高斯素数，因为它被1 + i整除。
任意高斯整数可以唯一地分解为一个单位和一系列真高斯素数的乘积。
例如，2 = -i(1 + i)2，以及1 + 3i = (1 + i)(2 + i)。
如果一个高斯整数的素数分解中不包含重复的真高斯素数，我们称这个高斯整数无平方因子。
因此在高斯整数中，2不是无平方因子的，而1 + 3i是无平方因子的。
根据定义，单位和高斯素数都是无平方因子的。
记f(n)为所有满足a2 + b2 ≤ n的无平方因子真高斯整数的数目。
例如，f(10) = 7因为1, 1 + i, 1 + 2i, 1 + 3i = (1 + i)(2 + i), 2 + i, 3和3 + i = -i(1 + i)(1 + 2i)是无平方因子的，而2 = -i(1 + i)2和2 + 2i = -i(1 + i)3不是。
已知f(102) = 54，f(104) = 5218以及f(108) = 52126906。
求f(1014)。