501 ** 八个约数 **

24 的八个约数是 1、2、3、4、6、8、12 和 24。 在不超过 100 的数中有十个数恰好有八个约数，分别是 24、30、40、42、54、56、66、70、78 和 88。 在不超过 n 的数中，记有 f(n) 个数恰好有八个约数。 已知 f(100) = 10，f(1000) = 180 以及 f(106) = 224427。 求 f(1012)。 502 ** 城堡计数 **

我们将高为 1、长为整数值的长方形成为方块，而将一系列按特定方式堆叠在一起的方块称为城堡。

在一个宽度为 w、高度为 h 的方阵上，按照如下方式构造城堡

1. 方块堆叠过程中不允许悬空或部分处于方阵之外。
2. 所有方块都与方阵对齐。
3. 在同一行的两个不同方块之间至少有一单位的间隔。
4. 最下方的一行必须包括一个长度为 w 的方块。
5. 最高高度恰好等于 h。
6. 必须由偶数个方块构成。

如下是 w=8 且 h=5 时的一个城堡： 给定方阵的参数 w 和 h，记所有有效的城堡数目为 F(w,h)。

例如，F(4,2) = 10，F(13,10) = 3729050610636，F(10,13) = 37959702514，以及 F(100,100) mod 1 000 000 007 = 841913936。

求 F(1012,100) + F(10000,10000) + F(100,1012) mod 1 000 000 007。 503 ** 妥协还是坚持 **

爱丽丝在玩一个用标有 1 至 n 的 n 张卡片进行的游戏。

这个游戏不断重复进行以下步骤： （1）爱丽丝随机地选择一张卡片。 （2）爱丽丝看不到这张卡片上的数，而她的一个朋友鲍勃可以看到，并告诉爱丽丝，在他之前看到过的数中，有多少个比这张卡片上的数要大。 （3）爱丽丝可以选择结束或继续游戏。如果她选择结束游戏，这个数将成为她的得分。如果她选择继续游戏，这张卡片从游戏中移除，并回到（1）。当游戏中没有卡片时，爱丽丝必须结束游戏。

记 F(n) 是爱丽丝采取 ** 最小化 ** 得分的最优策略时她的期望得分。

例如，F(3) = 5/3。在第一轮，她应当选择继续游戏，在第二轮，如果鲍勃告诉她前一个数比这一个数要大，她应选择结束游戏，否则她应选择继续游戏。

同样可以验证 F(4) = 15/8 以及 F(10) ≈ 2.5579365079。

求 F(106)，并将其四舍五入到小数点后 10 位小数作为你的答案。 504 ** 平方数个内部格点 **

四边形 ABCD 的四个顶点都是坐标轴上的格点，其坐标分别是：

A(a, 0), B(0, b), C(?c, 0), D(0, ?d)，其中 1 ≤ a, b, c, d ≤ m，且 a, b, c, d, m 均为整数。

可以验证，对于 m = 4，有 256 种构造 ABCD 的方式，在这 256 个四边形中，有 42 个严格地包含了平方数个格点在其内部。

对于 m = 100，有多少个四边形 ABCD 严格地包含了平方数个格点在其内部？ 505 ** 双向递归 **

记： x(0)=0 x(1)=1 对于，其中是下取整函数 x(2k)=(3x(k)+2x(⌊k2⌋)) mod 260 对于 k≥1，其中⌊ ⌋是下取整函数 对于 x(2k+1)=(2x(k)+3x(⌊k2⌋)) mod 260 对于 k≥1 yn(k)=x(k) if k≥n yn(k)=260−1−max(yn(2k),yn(2k+1)) if k<n A(n)=yn(1)

已知： x(2)=3 x(3)=2 x(4)=11 y4(4)=11 y4(3)=260−9 y4(2)=260−12 y4(1)=A(4)=8 A(10)=260−34 A(103)=101881

求 A(1012)。 506 ** 钟摆序列 ** 考虑下面这个无限重复的数字序列： 1234321234321234321... 神奇的是，你可以将这个序列分解成一个整数的序列，使得第 n 个整数的各位数字之和恰好是 n。

这个整数序列如下所示： 1, 2, 3, 4, 32, 123, 43, 2123, 432, 1234, 32123, ... 记 vn 是这个整数序列的第 n 个整数，例如，v2 = 2，v5 = 32，以及 v11 = 32123。

记 S(n) 为 v1 + v2 + … + vn。例如，S(11) = 36120，以及 S(1000) mod 123454321 = 18232686。

求 S(1014) mod 123454321。 507 ** 最短向量 **

记如下数列 tn 为 ** 三阶斐波那契 ** 数列： t0=t1=0； t2=1； tn=tn−1+tn−2+tn−3 for n≥3 并记 rn=tn mod 107。

向量 Vn=(v1,v2,v3) 和 Wn=(w1,w2,w3) 分别满足 v1=r12n−11−r12n−10,v2=r12n−9+r12n−8,v3=r12n−7·r12n−6 和 w1=r12n−5−r12n−4,w2=r12n−3+r12n−2,w3=r12n−1·r12n。 向量 D=k·Vn+l·Wn 的曼哈顿长度的计算方式为 |k·v1+l·w1|+|k·v2+l·w2|+|k·v3+l·w3|。 对于所有的整数 k 和 l 且 (k,l)≠(0,0)，我们记 S(n) 为向量 D 的最小曼哈顿长度。

第一对向量 V1 和 W1 分别是 (-1, 3, 28) 和(-11, 125, 40826)。 已知 S(1)=32，以及Σn=110S(n)=130762273722。

求Σn=120000000S(n)。 508 **i-1 进制的整数 **

考虑高斯整数 i-1，我们定义任意高斯整数 a+bi 的 **i-1 进制表示 ** 为一个有限的数字序列 dn-1dn-2…d1d0 满足：

• a+bi = dn-1(i-1)n-1 + dn-2(i-1)n-2 + … + d1(i-1) + d0
• 每个 dk 都在集合 {0,1} 中
• 没有前导零，也就是说，除非 a+bi 本身为 0，否则 dn-1 ≠ 0

以下是一些高斯整数的 i-1 进制表示：

11+24i → 111010110001101 24-11i → 110010110011 8+0i → 111000000 -5+0i → 11001101 0+0i → 0

值得注意的是，每个高斯整数都有唯一的 i-1 进制表示！

定义 f(a+bi) 为高斯整数 a+bi 的 i-1 进制表示中 1 的个数。例如，f(11+24i) = 9，以及 f(24-11i) = 7。

对于所有满足 | a| ≤ L 和 | b| ≤ L 的整数 a 和 b，定义 B(L) 为所有 f(a+bi) 的和。例如，B(500) = 10795060。

求 B(1015) mod 1 000 000 007。 509 ** 约数取石子游戏 **

安东和伯特兰很喜欢玩三堆取石子游戏。 然而，在玩了许多次之后，他们觉得过于无聊，打算修改一下游戏规则。 他们约定，从一堆中取出的石子数目，必须是这一堆石子数目的真约数。 例如，如果其中一堆目前有 24 颗石子，他们就只能从中取出 1、2、3、4、6、8 或 12 颗石子。 因此，如果一堆中只剩一颗石子，那么他们不能将这颗石子取走，因为 1 不是 1 的真约数。 谁先无法再取走石子谁就输了。 当然，安东和伯特兰两个人都会采取最佳策略。

三元组 (a,b,c) 表示这三堆石子分别的数目。 对于所有 1 ≤ a, b, c ≤ n，记 S(n) 为所有必胜态的数目。 已知 S(10) = 692 以及 S(100) = 735494。 求 S(123456787654321) modulo 1234567890。 510 ** 相切的圆 **

圆 A 和圆 B 彼此相切，同时和直线 L 也分别相切，三个切点互不相同。 圆 C 在 A、B 和 L 之间，且与这三者都相切。

分别记圆 A、B 和 C 的半径为 rA、rB 和 rC。 对于所有满足 0 <rA ≤ rB ≤ n，且 rA、rB 和 rC 均为整数的可行解，我们定义 S(n) = Σ rA + rB + rC。

对于 0 <rA ≤ rB ≤ 5，唯一解是 rA = 4，rB = 4，rC = 1，所以 S(5) = 4 + 4 + 1 = 9。

此外还已知 S(100) = 3072。 求 S(109)。