401 ** 约数的平方和 **

6 的约数有 1、2、3 和 6。 这些数的平方和是 1+4+9+36=50。

我们记 sigma2(n) 是 n 的所有约数的平方和。因此 sigma2(6)=50.

我们记 SIGMA2 是 sigma2 的和函数，也就是说 SIGMA2(n)=∑sigma2(i)，其中 i=1~n。 SIGMA2 的前 6 项为：1、6、16、37、63 和 113。

求 SIGMA2(1015) 模 109 取余的值。

402

** 值为整数的多项式 **

可以验证，对于任意整数 n，n4 + 4n3 + 2n2 + 5n 是 6 的倍数，而 6 是最大的满足这一性质的整数。

若对于任意整数 n，n4 + an3 + bn2 + cn 是整数 m 的倍数，记 M(a, b, c) 为 m 的最大值。例如，M(4, 2, 5) = 6。

记 S(N) 是所有满足 0 < a, b, c ≤ N 的 M(a, b, c) 的和。

我们可以验证 S(10) = 1972，以及 S(10000) = 2024258331114。

记 Fk 为斐波那契数列： F0 = 0，F1 = 1 并且对于任意 k ≥ 2 Fk = Fk-1 + Fk-2。

对于 2 ≤ k ≤ 1234567890123，求Σ S(Fk) 的最后 9 位数字。

403 ** 被双曲线和直线包围的格点 **

对于正整数 a 和 b，我们用 D(a, b) 表示被双曲线 y = x2 和直线 y = a·x + b 包围的区域： D(a, b) = { (x, y) | x2 ≤ y ≤ a·x + b }.

定义 L(a, b) 为 D(a, b) 内的格点数目。 例如，L(1, 2) = 8，以及 L(2, -1) = 1。

若整数对 (a, b) 满足 D(a, b)的面积是有理数，且 | a|,|b| ≤ N，我们定义所有相应的 L(a, b)的和为 S(N)。 我们可以验证 S(5) = 344 以及 S(100) = 26709528。

求 S(1012)。将你的答案模 108 取余。 404 ** 交错的椭圆 **

Ea 是一个椭圆，其方程为 x2 + 4y2 = 4a2。 Ea‘是将 Ea 绕原点 O(0, 0) 逆时针旋转角θ得到的图形，其中 0° < θ < 90°。 b 是两个椭圆离原点较近的两个交点到原点的距离，而 c 是另外两个较远的交点到远点的距离。 如果有序三元组 (a, b, c) 中 a、b 和 c 均为正整数，我们称之为规范椭圆三元组。 例如，(209, 247, 286) 就是一个规范椭圆三元组。

记 C(N)为所有满足 a ≤ N 的规范椭圆三元组 (a, b, c) 的数目。 可以验证 C(103) = 7，C(104) = 106，以及 C(106) = 11845。

求 C(1017)。 405 ** 给长方形铺地砖 **

我们希望给一个长是宽的两倍的长方形铺上地砖。 T(0) 表示只用一个长方形的铺法。 对于 n > 0，T(n) 表示以 T(n-1) 为基础，将后者的每一块地砖作如下替换得到的新铺法： 以下动画演示了 n 从 0 到 5 时的 T(n)： 记 f(n) 是 T(n) 中有四块地砖相遇的点的数目。 已知 f(1) = 0，f(4) = 82，以及 f(109) mod 177 = 126897180。

当 k = 1018 时，求 f(10k)，并将其模 177 取余作为你的答案。 406 ** 猜数游戏 **

我们尝试通过提问来确定整数集合 {1, 2, …, n} 中的某个特定数。每次提问时我们说一个数，可能会得到下面三个回答中的一个：

• “你的猜测比准确数要小。”（同时你需要付出成本 a），或者
• “你的猜测比准确数要大。”（同时你需要付出成本 b），或者
• “你猜对了！”（游戏结束）。

给定 n, a 和 b 的值，可以找到 * 最优策略 * 最小化在最差的可能情况下的总成本。

例如，如果 n = 5, a = 2，以及 b = 3，那么我们第一次提问应该猜 “2”。

如果 2 比准确数要大（付出成本 b=3），我们就知道 “1” 是准确数（总成本为 3）。 如果 2 比准确数要小（付出成本 a=2），我们下一次提问猜 “4”。 如果 4 比准确数要大（付出成本 b=3），我们确信 “3” 是准确数（总成本为 2+3=5）。 如果 4 比准确数要小（付出成本 a=2），我们确信 “5” 是准确数（总成本为 2+2=4）。 因此，这个策略的最差情况总成本是 5。可以证明这也是最小的最差情况总成本。事实上，以上描述的就是在一个给定的 n, a 和 b 值下的最优策略。

记 C(n, a, b) 是在给定 n, a 和 b 值下最优策略的最差情况总成本。

如下是其中一些例子： C(5, 2, 3) = 5 C(500, √2, √3) = 13.22073197… C(20000, 5, 7) = 82 C(2000000, √5, √7) = 49.63755955…

记 Fk 是斐波那契数：Fk = Fk-1 + Fk-2，起始条件为 F1 = F2 = 1。 求∑1≤k≤30 C(1012, √k, √Fk)，并将答案四舍五入到小数点后八位小数。 407 ** 幂等元 **

对于 0 ≤ a ≤ 5，分别计算 a2 mod 6，我们得到： 0,1,4,3,4,1。

使得 a2 ≡ a mod 6 的最大 a 值为 4。 我们用 M(n) 表示使得 a2 ≡ a (mod n) 的最大的 a < n。 因此 M(6) = 4。

对于 1 ≤ n ≤ 107，求∑M(n)。 408 ** 穿越方格的容许路径 **

我们称格点 (x, y) * 不容许的 *，如果 x, y 和 x + y 均为正平方数。 例如，(9, 16)是不容许的， 而 (0, 4), (3, 1) 和(9, 4)都不是。

考虑从点 (x1, y1) 到点 (x2, y2) 的路径，路径上每次只能往北或往东走一步。 我们称路径是 * 容许的 *，如果路径经过的点都不是不容许的。

记 P(n)为从 (0, 0) 到(n, n)的容许路径总数。 可以验证 P(5) = 252, P(16) = 596994440 以及 P(1000) mod 1 000 000 007 = 341920854。

求 P(10 000 000) mod 1 000 000 007。

409 ** 极限取石子游戏 **

记 n 为正整数。考虑如下的 ** 取石子游戏 ** 设计：

• 有 n 个非空的堆。
• 每个堆的石子数小于 2n。
• 没有两堆的石子数相同。

记 W(n) 是所有设计中必胜态的数目（必胜态是指先手玩家有必胜策略的状态）。例如，W(1) = 1, W(2) = 6, W(3) = 168, W(5) = 19764360，以及 W(100) mod 1 000 000 007 = 384777056。

求 W(10 000 000) mod 1 000 000 007。

410

** 圆与切线 **

记 C 为半径为 r 的圆，其方程为 x2 + y2 = r2。我们选取两个点 P(a, b) 和 Q(-a, c)，使得过 PQ 的直线与圆 C 相切。

例如，四元组 (r, a, b, c) = (2, 6, 2, -7) 就满足上述性质。

记 F(R, X)是满足上述性质的整数四元组 (r, a, b, c) 的数目，要求 0 < r ≤ R 且 0 < a ≤ X。

可以验证 F(1, 5) = 10, F(2, 10) = 52 以及 F(10, 100) = 3384。 求 F(108, 109) + F(109, 108)。