用$I_r$表示以原点为圆心，半径为r的圆内部的所有整数格点$(x,y)$，即 $$I_r=\{(x,y)\in\mathbb Z^2: x^2+y^2 < r^2\}.$$ 例如$I_2$中包含了$(0,0), (1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1)$共九个点，以之为顶点可以构造出八个包含原点在内部的三角形，下图是其中的两个，其它三角形都可以通过旋转这两个三角形得到：

以$I_3$中的点为顶点，则可以构造出360个内部包含原点的三角形，对于$I_5$则可以构造10600个。

以$I_{105}$中的点为顶点，可以构造出多少个内部包含原点的三角形？

本题难度:

解答

记O为原点，并将$I_{105}$与包含x轴正半轴的上半平面的交集记作H： $$H=\{(x,y)\in I_{105}: y\ge0\}\cup \{(x,0)\in I_{105}: x>0\}.$$ 令$A,B,C$为H中能组成三角形的三点，不失一般性可以按照$OA, OB, OC$的幅角（与x轴正半轴的夹角）递增的顺序来标记这三个点。

令$A',B',C'$分别为$A,B,C$关于原点的对称点，$H'$为$H$关于原点的对称集，则$\Delta ACB'$和$\Delta BA'C'$这两个三角形都包含原点。

反之任意包含原点的三角形或者有一个顶点在$H'$中，或者有两个顶点在$H‘$中，取这些顶点关于原点的对称点就得到H中的一个三角形。

为便于计数，先遍历$H$中的点，将其按幅角分组，记$d(k)$为幅角为k的点的总数，再记

\begin{align} s_1&=\sum_kd(k) \\ s_2&=\sum_kd^2(k) \\ s_3&=\sum_kd^3(k) \\ \end{align} 则共有$s_1^3$种取三个点的方式，其中需要排除至少有两点共线的情况，这些情况中三点共线又多扣除了两次需要再加回，如此则得下式中的分子。

结果与选点的顺序无关，因此除以三个点排列$3!$。最后，每组点能生成两个符合要求的三角形，因此再乘以2。

综上即得： $$\frac{s_1^3-\binom{3}{2}s_1s_2^2+2s_3}{3!}\cdot 2=1725323624056.$$ 注：本题的解答修订自该帖。

import fractions

d={0:104}

for x in range(-104,105):
    for y in range(1,105):
        if x*x+y*y < 105*105:
            m=fractions.gcd(x,y)
            d[(x/m,y/m)]=d.get((x/m,y/m),0)+1

s1=sum(d[k] for k in d)
s2=sum(d[k]*d[k] for k in d)
s3=sum(d[k]*d[k]*d[k] for k in d)

print (s1*s1*s1-3*s1*s2+2*s3)/3