图形学问题--内摆线及格点问题（困惑很久的题目！求高手支招！！）

mathe

现在我们查看$r_1,r_2$互素的情况。我们看第一类切皮雪夫多项式$T_n(x)$有$T_n(cos(x))=cos(nx)$。而且存在整系数首一多项式$h(x)$使得$2T_n(x)=h(2x)$,由此得出$2cos(nx)=h(2cos(x))$

mathe

于是我们得出如果$2cos(h)$的分母为c,那么$2cos((r_1+r_2)h)$的分母必然是$c^(r_1+r_2)$

mathe

结合9#和12#结论容易得出c=1,由于余弦1/2是正弦是无理数，只能$cos(h)$是整数,于是我们知道$h$必然是$pi/2$的倍数,我们设这个倍数为$k$
所以我们可以写成
$x+yi=(R-r)*i^{{kr}/d}+r*(-i)^{{k(R-r)}/d}=(R-r)*i^{kr_1}+r*(-i)^{kr_2}$,其中$d=gcd(R,r)$
我们可以分别取$k=0,1,2,3$得出4个解，也就是对于每个给定的(R,r),总是四组解。而对应的$|x|+|y|$总是$R$或$R-2r$,分情况讨论即可
其中k=0,得出$x+yi=R,|x|+|y|=R$
     k=1,3时，如果$r_1,r_2$一奇一偶，那么$|x|+|y|=R$
                  如果$r_1,r_2$同为奇数，那么模4同余时，$|x|+|y|=R-2r$,如果模4不同，那么$|x|+|y|=R$
   k=2时，如果$r_1,r_2$同奇数，那么$|x|+|y|=R$,如果一奇一偶，那么$|x|+|y|=R-2r$
所以总体我们需要分三类
i)如果$r_1,r_2$一奇一偶，四个总和为4R-2r
     如果$r_1,r_2$同为奇数模4同余，四个和为4R-4r
     如果$r_1,r_2$同为奇数模4不同，四个和为4R

然后对于每个给定的R,我们需要计算所有对应的$r<R/2$对应结果的和，这个挺简单的，我们先求出R所含2的幂k,然后将所有r分成两类
i)r含2的幂不超过k次，对于这些r，设其2的幂为h，对应$R-r,r$含2的幂相同，所以$r_1,r_2$同为奇数
   对于这些，我们还需要分析$r_1,r_2$是否模4同余，也就是${R-r}/{2^h},r/{2^h}$模4是否同奇偶，也就是判断${R-r-2^h}/{2^{h+1}},{r-2^h}/{2^{h+1}}$是否同奇偶
ii)r含2的幂大于k次（实际上我们只要分析r为$2^{k+1}$的倍数即可),这时$r_1,r_2$一奇一偶。

mathe

而一楼给的例子中数据也有问题，由于r,R有公因子500，两边同时除500平方相加得，$(x/500)^2+(y/500)^2=13+12cos(3t)$,将x=772,y=2376代入得出$cos(3t)=3116/3125$于是cos(t)满足方程4x^3-3x=3116/3125不是有理数

mathe

13#漏了一种情况，还是按r分类更容易

mathe

对给定N，对于每个r,R-r取值在r+1到N-r共N-2r,每个贡献值平均值为4R-2r.其中N-r同r拥有相同2的幂的有$[{N-2r}/{2^{k+1}}]$其中k为r拥有的2的幂。这个数为偶数，那么我们只需要累加所以的4R-2r即可，但是如果是奇数，那么多了一对$r_1,r_2$异奇偶情况，需要补充一个2r

mathe

于是我们可以先计算平均值部分，为2(N+1+r)(N-2r),然后我们对这个表达式关于r求和，得到一个N的三次表达式
然后我们还需要判断每个r是否多一个$r_1,r_2$同奇偶情况，这个我们按r含的2的次幂k分类作比较好。也就是需要判断N-2r的第k+2比特是否为1，符合条件的r是公差为$2^{k+2}$的等差序列，同样可以算出。于是问题变成一个log(N)复杂度的算法问题

浪淘沙

#14楼：x=772,y=2376没问题，取t = 2 (-pi + ArcTan[3/4] + 2 pi ), 那么x=772,y=2376，cos(t)=7/25, sin(t)=24/25

浪淘沙

#5楼： 第一个参数方程有问题  x^2+y^2=r1^2 + r2^2 + 2 r1 r2 Cos[((r1 + r2) t)/r1]才对

mathe

14#弄错了，应该cos(5t)而不是cos(3t),所以弄错了。