← 完整题目索引

PROJECT EULER · #0556

无平方因子的高斯整数

Squarefree Gaussian Integers

仅题目 · 已解决原题 ↗

高斯整数是一个数字 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 整除。
z1z2=a1+b1ia2+b2i=(a1+b1i)(a2−b2i)(a2+b2i)(a2−b2i)=a1a2+b1b2a22+b22+a2b1−a1b2a22+b22i=a3+b3i
因此,如果 a1a2+b1b2a22+b22 和 a2b1−a1b2a22+b22 是整数,z1 可以被 z2 整除。
例如,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)。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。