滚动正方形-ProjectEuler 935

iseemu2009

滚动正方形

mathe

我们改设小正方形边长为1，大正方形边长为x.
于是我们可以发现经过[x]-1次以后，第一条边还余{x},下次滚动会用掉下一条边sqrt(1-{x}^2)长度，于是相当于余下长度为x2=x-sqrt(1-{x}^2),
于是这条边上再滚动若干次后余{x2}.
如果我们定义[0,1)上函数H(x)={x-sqrt(1-x^2)},那么我们首先需要找到H迭代4的倍数次的所有不动点，然后以此为基础就相对比较容易了

mathe

上面函数H(x)在[0,1)上是两段独立增函数，每段值域都从0到1取满，所以每次迭代分段数翻倍，迭代4m次后有2^(4m)段，对应内部不动点2^(4m)-1个

mathe

我们知道H(x)的唯一断裂点在\(x_{1,0}=\frac{\sqrt{2}}2\)
那么对于函数\(H_2(x)=H(H(x))\), 会有三个断裂点，除了\(x_{1,0}\)以外,还有一个\(0<x_{2,0}<x_{1,0},x_{1,0}<x_{2,1)}<1\)
很显然\(H(x_{2,0})=H(x_{2,1})=x_{1,0}\)
同样对于函数\(H_3(x)=H(H_2(x))\),除了前面三个断裂点，会增加4个断裂点\(x_{3,0},x_{3,1},x_{3,2},x_{3,3}\)满足\(0<x_{3,0}<x_{2,0}<x_{3,1}<x_{1,0}<x_{3,2}<x_{2,1}<x_{3,3}<1\)而且 \(H(x_{3,0})=x_{2,0},H(x_{3,1})=x_{2,1},H(x_{3,2})=x_{2,0},H(x_{3,3})=x_{2,1}\)
这个规律可以一直递推下去。

现在如果我们取\(x_{4m,0},x_{4m,1}, ...,x_{4m,2^{4m-1}-1}\), 那么经过4m轮迭代会返回0
而如果我们取正方形边长为\(h+x_{4m,k}\),其中h是一个整数，那么在第一条边上我们需要先额外翻h-1次，使得余下长度为\(x_{4m,k}\), 然后再翻一次，使得下一条边余下长度为为\(h+H(x_{4m,k})\)或\(h-1+H(x_{4m,k})\),前者还是后者依赖于\(x_{4m,k}\)是大于\(x_{0,0}\)还是小于\(x_{0,0}\),这个正好对应k的最高比特位是1或0，也就是如果k最高比特位是1，那么余下长度为\(h+H(x_{4m,k})\)，不然余下长度为\(h-1+H(x_{4m,k})\)
由此一次迭代下去，于是总共应该需要翻\(4m\times(h-1)+bitcount(k)\)次。
所以我们实际上需要统计对于哪些(m,k)组合可以使得我们翻转次数正好等于我们的目标值。
另外还有一种边长正好是整数h的情况，对应\(m=1,k=0,x_{0,0}=0\)需要翻转\(4m\times(h-1)\).
另外我们还需要考虑\(x_{2m+1,k}\)，以及\(x_{4m+2,k}\),这两者都需要迭代8m+4次。次数会稍微有些不同。

mathe

前面分析有些错误，不过主要思路还是没有问题的。
我们记小正方长边长为1，大正方形边长为h+x,其中h是整数，\(0\le x<1\)
记\(H_1(x)=x\)代表小正方形在第一条边翻滚到最后时，留下的长度。（第一条边上翻滚h-1次后正好留下长度x)
于是从第一条边翻滚到第二条边时，第一次使用了第二条边上边长\(\sqrt{1-H_1(x)^2}\),余下长度\(h+x-\sqrt{1-H_1(x)^2}\)
于是再翻滚h-1或h次，在第二条边上留下长度\(H_2(x)=\{x-\sqrt{1-H_1(x)^2}\}\),其中函数\({t}\)代表t的小数部分,特别在\(-1<t<0\)时，\({t}=1+t\)。
于是类似的，第三条边上留下长度为\(H_3(x)=\{x-\sqrt{1-H_2(x)^2}\}\),等等。

由于\(H_1(x)\)将[0,1)连续递增映射到[0,1), 而\(\sqrt{1-H_1(x)^2}\)将[0,1)连续递减映射到(0,1],
所以函数\(x-\sqrt{1-H_1(x)^2}\)将区间[0,1)连续递增映射到[-1,1)，所以\(H_2(x)\)是分段函数，其中每段都是连续递增函数，从0递增到1.
  这个间断点为\(x_{2,1}=\frac{\sqrt{2}}2\), 也就是\(H_2(x)\)在区间\([0,x_{2,1})\)递增映射到\([0,1)\)；同样在区间\([x_{2,1},1)\)上连续递增映射到\([0,1)\)

类似分析，\(\sqrt{1-H_2(x)^2}\)分别将区间\([0,x_{2,1})\)和\([x_{2,1},1)\)连续递减映射到\((0,1]\), 所以
   \(x-\sqrt{1-H_2(x)^2}\)将区间\([0,x_{2,1})\)连续递增映射到\([-1,x_{2,1})\), 将\([x_{2,1},1)\)连续递增映射到\([x_{2,1}-1,1)\)
  所以上面函数有两个零点\(x_{3,1},x_{3,2}\)而且\(0\lt x_{3,1} \lt x_{2,1}\lt x_{3,2}\lt 1\)。
于是\(H_3(x)\)将\([0,x_{3,1})\)连续递增映射到\([0,1)\), 将\([x_{3,1},x_{3,2})\)连续递增映射到\([0,1)\)，将\([x_{3,2},1)\)连续映射到\([0,1)\)。
   需要注意的是\(H_3(x_{2,1})={x_{2,1}-1}=x_{2,1}\).

类似，我们有\(H_4(x)\)和三个零点\(x_{4,1},x_{4,2}=x_{2,1},x_{4,3}\) 满足\(0\lt x_{4,1}\lt x_{3,1}\lt x_{4,2}=x_{2,1} \lt x_{3,2} \lt x_{4,3} \lt 1\).
...

于是对于任意的m,我们可以看出，当x初始值选择为\(x_{4m,k}\)而且k不为4的倍数时，对于边长为h+x的情况，我们可以经过若干次翻滚，其中每条边经历m次，可以首次返回原始位置。
而每条边上都需要翻滚h或h+1次，
第一条边总是翻滚h次到达第二条边。后面第d条边上翻滚次数是h还是h+1次，取决于\(x_{4m,k}-\sqrt{1-H_{d-1}(x_{4m,k})^2}\)的正负性。

mathe

由于函数\(x-\sqrt{1-H_{d-1}(x)^2}\)将\([x_{d-1,s-1},x_{d-1,s})\)单调递增映射到\([x_{d-1,s-1}-1,x_{d-1,s})\),其中唯一零点为\(x_{d,s}\)
所以上面的符号判断实际上需要我们找到s使得\(x_{d-1,s-1}<x_{4m,k}<x_{d-1,s}\)并且判断\(x_{4m,k}\)和\(x_{d,s}\)的大小关系，
这需要我们找出所有\(x_{u,v}\)之间顺序关系。
实际上我们很容易证明，\(x_{us,vs}=x_{u,v}\),由此如果我们需要比较\(x_{u_1,v_1}\)和\(x_{u_2,v_2}\)的大小关系，那么我们只需要比较\(x_{u_1v_2,v_1v_2}\)和\(x_{u_2v_1,v_1v_2}\)的大小关系，也就是比较\(u_1v_2\)和\(u_2v_1\)的大小关系，等价于比较\(\frac{u_1}{v_1},\frac{u_2}{v_2}\)的大小关系，这个使得上面不等式判断关系变得非常简单。

mathe

我们现在可以查看边长为\(h+x_{u,v}\)其中\((u,v)=1\)的情况。
这种情况我们知道在到达第u条边时第一次正方形又正好落在某个角落上。
第一条边滚动h次到达第二条边，第2条到第u-1条边分别再滚动h或h+1次到达下一条边，而最后一条边还需要再滚动h次落到角落。
所以我们需要判断对于d=2,...,u-1, 分别滚动h还是h+1次到达下一条边，于是，我们需要判断
\(x_{u,v}-\sqrt{1-H_{d-1}(x_{u,v})^2}\)的正负性。所以我们需要找到s使得\(x_{d-1,s-1}\lt x_{u,v} \lt x_{d-1,s}\)
也就是要求\(\frac{s-1}{d-1}\lt \frac vu\lt \frac{s}{d-1}\), 即\(s-1=\lfloor \frac{v(d-1)}u\rfloor\)
这时，我们要比较\(\frac{v}{u}\)同\(\frac{s}{d}\)的大小关系。如果\(\frac{v}{u}\gt \frac{s}{d}\),那么\(x_{u,v}-\sqrt{1-H_{d-1}(x_{u,v})^2}\gt 0\),所以需要滚动h+1次，不然滚动h次。所以最总滚动次数为\(h\times u+\sum_{d=2}^{u-1} (\frac{v}{u} \gt \frac{1+\lfloor \frac{v(d-1)}u\rfloor}d)=h\times u+\sum_{d=2,0<(vd)\pmod u\lt v}^{u-1}1=h\times u+v-1\)
然后我们对u进行分类，为了计算f(n)
如果u是4的倍数，我们只需要统计所有的\(h\times u+v-1\le n\)的数目,其中\(h\ge 1,1\le v\lt u, (u,v)=1\); 这部分等于\([u,n+1]\)中同u互素的整数个数
如果u除以4余数为2，我们需要统计所有的\(2(h\times u+v-1)\le n\)的数目,其中\(h\ge 1,1\le v\lt u, (u,v)=1\). 这部分等于\([u,\lfloor \frac n2\rfloor+1]\)中同u互素的整数个数
如果u是奇数，我们需要统计所有的\(4(h\times u+v-1)\le n\)的数目,其中\(h\ge 1,1\le v\lt u, (u,v)=1\). 这部分等于\([u,\lfloor \frac n4\rfloor+1]\)中同u互素的整数个数。

(15:32) gp > ff(10)
%68 = 10
(15:32) gp > ff(100)
%69 = 805
(15:32) gp > ff(1000)
%70 = 76433
(15:32) gp > ff(10000)
%71 = 7603847
(15:32) gp > ff(100000)
%72 = 759954487

iseemu2009

1、按照你的方法，有没有出现 b 取某值时，小正方形一直循环滚动，就是不能回到初始位置的情况？
2、可否给出8步内回到初始位置时，所有b的取值？我来验证一下。

iseemu2009

iseemu2009 发表于 2025-5-9 15:43
1、按照你的方法，有没有出现 b 取某值时，小正方形一直循环滚动，就是不能回到初始位置的情况？
2、可否给 ...

按照7#的结果，你应该是编程解出这道题了？

mathe

前面的ff结果列表:
2 0
3 0
4 3
5 3
6 4
7 4
8 8
9 8
10 10
11 10
12 17
13 17
14 19
15 19
16 26
17 26
18 30
19 30
20 39