作者tml (流刑人形)
看板puzzle
标题[中译] ProjectEuler 450 Hypocycloid and Latti
时间Fri Dec 20 04:28:57 2013
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)。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 129.2.129.152