高斯整数

高斯整数是形如$a+bi$且a和b均为整数的复数(i是虚数单位，即$i^2=-1$)。

取$b=0$即一般意义上的整数，为方便区分我们将满足$b=0$的高斯整数称为有理整数。

若两个高斯整数的积为有理整数，则称这两个高斯整数为该有理整数的约数。例如 $$5=(1+2i)(1-2i)=(1+i)(\frac{5}{2}-\frac{5}{2}i),$$ 因此$1\pm 2i$都是5的约数,而$1+i$不是5的约数。显然，若$a+bi$是某个有理整数的约数，那么其共轭$a-bi$必定也是该有理整数的约数。

事实上，5一共有六个具有正实部的约数：$\{1,5,1\pm2i, 2\pm i\}$，以下列出了前五个正有理整数的所有具有正实部的约数：

$n=1$，正实部约数$\{1\}$，约正实部数和$s(n)=1$，

$n=2$，正实部约数$\{1,2,1\pm i\}$，正实部约数和$s(n)=5$，

$n=3$，正实部约数$\{1,3\}$，正实部约数和$s(n)=4$，

$n=4$，正实部约数$\{1,2,4,2\pm 2i,1\pm i\}$，正实部约数和$s(n)=13$，

$n=5$，正实部约数$\{1,5,1\pm2i,2\pm i\}$，正实部约数和$s(n)=12$。

以上正实部约数之和为35。可以验证 $$\sum_{n=1}^{10^5}s(n)=17924657155.$$ 求$\sum_{n=1}^{10^8}$。

本题难度:

解答

显然这些约数和分成两部分，有理整数约数的和非有理整数约数的和。

容易看出每个有理整数约数x在和式中出现$\lfloor10^8/x\rfloor$次，因此它们的和是 $$\sum_{x=1}^{10^8}\lfloor10^8/x\rfloor\cdot x.$$ 现设$z=x+yi$ $(y\neq0)$是n的一个非有理整数约数，则显然$x-yi$, $y\pm xi$也都是n的约数，因此不妨设$x\ge y$。

令$d=\gcd(x,y)$、$x=ad$、$y=bd$则有 $$\frac{n}{x+yi}=\frac{n}{d(a+bi)}=\frac{n}{d(a^2+b^2)}(a-bi),$$ 显然$a/(a^2+b^2)$和$b/(a^2+b^2)$都不是有理整数，因此$a^2+b^2$必须是n的约数。

此外，对d的每个大于1的约数$d_i$，$a/d_i$和$b/d_i$中至少有一个不是有理整数，否则$\gcd(x,y)$应是$dd_i$，因此$d_i$也需要能整除n，从而d也是n的约数。

反之若$d(a^2+b^2)$能整除n，则等式右侧显然是高斯整数。

构筑字典，以$a^2+b^2$为键，$2a+2b$（即$a\pm bi$与$b\pm ai$的和）为值，有理整数的情况可以归约为$b=0,a=1$，而$x=y$的情况可以归约为$z=d(1+i)$，因此$s[1]=2$，$s[2]=2$。

最后如同有理整数约数的情况，缩放s的键和值并统计每个非有理整数约数出现的次数再汇总即可得结果$17971254122360635$。

import math

target=10**8

s={1:1,2:2}
for a in range(2,10**4+1):
    b=1
    c=a*a+b*b
    while b < a and c<=target:
        if math.gcd(a,b)==1:
            s[c]=s.get(c,0)+2*a+2*b
        b+=1
        c=a*a+b*b

print(sum(sum(s[c]*(k//c)*(target//k) for k in range(c,target+1,c)) for c in s))