ProjectEuler 450 Hypocycloid and Latti - 拼圖

450. Hypocycloid and Lattice points

http://projecteuler.net/problem=450

內擺線是讓一小圓在一大圓內滾動，小圓上的一點所描繪出的軌跡。

令大圓的圓心在原點，並假設起始點在最右端，則其參數式可表為

x(t) = (R-r) cos(t) + r cos((R-r)t/r)
y(y) = (R-r) sin(t) - r sin((R-r)t/r)

其中R和r分別為大小圓的半徑。

令C(R,r)為由R和r定義出的內擺線中，其坐標為整數、且存在t值使sin(t)和cos(t)皆為
有理數的點的集合。

令S(R,r) = Σ|x|+|y|對所有(x,y)∈C(R,r)的和。

令T(N) = ΣS(R,r)對所有3≦R≦N，1≦r≦R/2的和。

已知：
C(3, 1) = {(3, 0), (-1, 2), (-1,0), (-1,-2)}。

C(2500, 1000) = {(2500, 0), (772, 2376), (772, -2376), (516, 1792),
(516, -1792), (500, 0), (68, 504), (68, -504),　(-1356, 1088),
　　　　　　　　 (-1356, -1088), (-1500, 1000), (-1500, -1000)}。

注意：(-625, 0)並不是集合C(2500, 1000)的一個元素因為對應的sin(t)值不為有理數。

S(3, 1) = (|3| + |0|) + (|-1| + |2|) + (|-1| + |0|) + (|-1| + |-2|) = 10

T(3) = 10
T(10) = 524
T(100) = 580442
T(10^3) = 583108600

請求出T(10^6)。

--