Project Euler 口胡记录

作者: HiCyanic | 来源:发表于2018-09-01 22:44 被阅读0次

看不懂

261

319

465

367
492
251
276

394
503
360
245

388
513
273
447

302
518
379
508

369
550
499

Solutions

题号标 x 的需要看证明 / 重新思考 / 写代码

Problem 110 Diophantine reciprocals II

在如下方程中， $x,y,n$ ，均为正整数（其中 $x \le y$ ）
$\frac 1 x + \frac 1 y = \frac 1 n$
不同的解的总数超过四百万种的最小 $n$ 值是多少？

Solution

此题有一个优美的结论：此方程组的解数为 $\frac {d(n^2) + 1} 2$

proof

考虑 $b = \frac {an} {a-n}$ 是整数，又由于 $an - n(a-n) = n ^2 \ \Longrightarrow \ \gcd(an,a-n) \mid n^2$

$\gcd (an, a-n) = a-n$ ，得到 $a - n \mid n^2$ 。那么令 $a = n + t$ ， $t$ 就是 $n^2$ 的一个约数，易得这是一个充要条件

令 $n = 2^{p_1} 3 ^{p_2} 5^{p_3}$ ，注意到 $d(n^2) = \prod (2p_i + 1)$ ，那么最优解一定有 $p_1 \ge p_2 \ge \cdots$ ，以此作为剪枝即可。

参考资料

Problem 233x Lattice points on a circle

作过点 $(0,0)$ 、 $(N,0)$ 、 $(0,N)$ 和 $(N,N)$ 的圆，记圆周上坐标为整数的点的数目为 $f(N)$ 。

有些正整数 $N \le 10^{11}$ 且 $f(N) = 420$ ，这些正整数的和是多少？

Solution

考虑到 $n^2$ 需要表示为两个数的平方和。这里有 费马平方和定理

一个奇质数能表示为两个数的平方和的充要条件是
$p \equiv 3 \pmod 4$

根据经典恒等式 $(a^2 + b^2)(c^2 + d^2) = (ac+bd)^2 + (ad-bc)^2$ ，可以得到：这种质数的乘积也能表示为两个平方数的和。
分解 $\frac {420} 4 = 105$ 后讨论，最后转化为一个线性筛DP（考虑每个这种质数的指数）

参考资料

Note 事实上，任意一个 $4k+1$ 素数都能 唯一的 表示为两个数的平方和。这是因为 高斯整数环 是一个欧氏环，满足唯一分解性，具体参见高代书的内容

Problem 271 Modular Cubes, part 1

对于正整数 $n$ ，存在整数 $x$ ，满足 $1<x<n$ ，且 $x^3 \equiv 1 \pmod n$ 。记所有这样的整数 $x$ 的和为 $S(n)$ 。

求 $S(13082761331670030)$ 。

Solution

注意到将模数分解后，每个质因子独立（这些质因子都很小），于是求出每一个质因子下的三次剩余，暴力 CRT 合并即可

Problem 272x Modular Cubes, part 2

对于正整数 $n$ ，存在整数 $x$ ，满足 $1<x<n$ ，且 $x^3 \equiv 1 \pmod n$ 。记所有这样的整数 $x$ 数目为 $C(n)$ 。

对于所有使得 $C(n)=242$ 的正整数 $n \le 10^{11}$ ，求它们的和。

Solution

考虑三次剩余的性质，并注意到 $253=3^5$ （实际上一定是3的幂次）

三次剩余的性质：
$\begin{split} d(p) &= 1 \\ d(p^n) &= 3 \\ d(p^n) &= 3 \quad\quad p \equiv 1 \pmod 3 \\ d(p^n) &= 1 \quad\quad p \equiv 2 \pmod 3 \\ \end{split}$

参考资料 1

参考资料 2

参考资料 3

Problem 292 Pythagorean Polygons

我们定义 毕达哥拉斯多边形 为满足下列性质的凸多边形：

有至少三个顶点，

不存在三个顶点共线，

每个顶点坐标均为整数，

每条边长度均为整数。

对于给定的整数 $n$ ，记 $P(n)$ 为边长 $\le n$ 的不同毕达哥拉斯多边形的数目。
只要不能将其中一个通过平移得到另一个，就被认为是不同的毕达哥拉斯多边形。

求 $P(120)$ 。

Solution

显然可以得到一个DP做法，利用毕达哥拉斯三元组转移。

注意到条件 不存在三个顶点共线，于是考虑本原毕达哥拉斯三元组，所有三元组都可以由这个东西生成，于是用这个东西转移即可，由于斜率的单调性，可以前缀和优化一下

Problem 295 Lenticular holes

若两圆重叠而成的凸区域满足以下条件，我们称之为 透镜孔洞

两圆的中心都是格点。

两圆在两个格点处相交。

两圆重叠而成的凸区域内部不包含任何格点。

如果存在两个半径分别为 $r_1$ 和 $r_2$ 的圆能够生成透镜孔洞，我们就称有序正实数对 $(r_1, r_2)$ 为透镜数对。

记 $L(N)$ 是所有满足 $0<r1\le r2 \le N$ 的不同透镜数对的数目。

求 $L(100 000)$ 。

Solution

通过 不等式 得到了长度的上界。考虑其中垂线，根据限制，是一段区间， $\gcd$ 即可

Problem 341 The Mouse on the Moon

考虑一个 $500 \times 500$ 的网格，中心有一个半径为 $250$ 的网格，要求选择一个多边形，与圆不相交（可以相切），并且顶点都在整点上，求包围面积与周长的最大比值。

[站外图片上传中...(image-71e329-1535885869188)]

Solution

分数规划好题！

二分答案，观察到一条边的贡献，可以由叉积减去答案乘长度得到，利用凸多边形的性质，按照 $x$ 排序，DP 即可

Problem 362x Squarefree factors

我们记 $F_{sf}(n)$ 是将 $n$ 分解为一个或多个大于 $1$ 的无平方因子因数乘积的方式数。

记 $S(n)$ 为 $\sum _{k=1} ^{n} F_{sf}(k)$ 。求 $S(10^{10})$ 。

Solution

首先线性筛出无平方因子数，考虑暴力DP， $f(i,j)$ 考虑 $[1,i]$ 中，用不超过 $p[j]$ 无平方因子数表出的个数。
然而这样暴力大概是 $O(n \sqrt n)$ 的。

注意到我们只需要考虑到根号级别的质数（因为大于根号的至多只有一个），其他的前缀和算一算，复杂度就是 $O(n)$ 的了

Problem 373 Circumscribed Circles

每个三角形都有一个经过三个顶点的外接圆。考虑所有外接圆半径也是整数的整数边长三角形。

取其中外接圆半径不超过 $n$ 的三角形，记它们的外接圆半径之和为 $S(n)$ 。

求 $S(10^7)$ 。

Solution

通过××可以发现，一个结论：这种三角形的三边，一定是毕达哥拉斯三元组的直角边。

proof

考虑一个三角形 $ABC$ ，他的圆心为 $O$ 。考虑作过 $A$ 的直径 $AD$ ，连 $AD, BD$ 。

根据托勒密定理，有：
$a \sqrt {4r^2 - b^2} + b \sqrt {4r^2 - a^2} = 2rc$
于是根号下的东西是完全平方数。

由于小于 $n$ 的毕达哥拉斯三元组是 $O(n)$ 级别的，所以暴力生成三元组，枚举半径， $a,b$ ，求出 $c$ ，即可。

Note 似乎存在规律：两个 $r_1, r_2$ ，如果它们的分解当中 $4k+1$ 素数的指数分布相同，它们的答案相同。（如何证明？）

Problem 416 A frog’s trip

在一列 $n$ 个方块的最左边一个上有一只青蛙。青蛙通过连续不断的跳跃，先跳到最右边的方块，然后再跳回最左边的方块。它向右跳的时候每次可以跳一个、两个或三个方块，跳回来时也同理。它不能跳出这些方块。这样的往返它一共进行了 $m$ 次。

记 $F(m, n)$ 为青蛙在旅途中至多有一个方块从未被跳到过的方式总数。

求 $F(10, 10^{12})$ 的最后 $9$ 位数字。

Solution

把从右向左跳的青蛙反转方向，所有 $20$ 只一起考虑，可以矩阵快速幂解决。

状态只需维护两个位置的青蛙数量，剩下一个可以直接得到。

Hardest

Problem 446 Retractions B*

对于任意整数 $n>1$ ，函数族 $f_{n,a,b}$ 按如下方式定义： $f_{n,a,b}(x) \equiv ax+b \pmod n$ ，其中 $a,b,x$ 都是整数，且 $0<a<n，0 \le b<n，0 \le x<n$ 。

我们称 $f_{n,a,b}$ 为撤销函数，当 $0\le x<n$ 均有在模 $n$ 意义下 $f_{n,a,b}(f_{n,a,b}(x)) \equiv f_{n,a,b}(x)$ 。

记 $R(n)$ 是给定 $n$ 下撤销函数的数目。记 $F(N)=\sum R(n^4+4)$ ，其中 $1 \le n \le N$ 。

求 $F(10 ^7) \pmod {1 000 000 007}$

Solution

首先可以证明一个结论：
$R(n) = \prod (p_i^{k_i} + 1) - n, \quad \quad n= p_1^{k_1} p_2^{k_2} p_3^{k_3} \cdots$

proof

考虑 $a(ax+b)+b \equiv ax + b \pmod n$ 等价于 $a(a-1)x+ab \equiv 0 \pmod n$ 。

令 $x$ 分别等于 $0, 1$ ，容易得到 $n \mid a(a-1)$ 并且 $n \mid ab$ ，显而易见，这是个充分必要条件。

令 $d = \gcd(a, n)$ ，那么有 $b$ 存在 $d$ 种取值（ $b$ 是 $\frac n d$ 的倍数），并且 $\frac n d \mid a - 1$ 。

注意到 $x \cdot \frac n d + 1 = a = y \cdot d$ ，根据扩欧，容易得到：当且仅当 $\gcd(d, \frac n d) = 1$ 时，存在解 $a$ ，并且解唯一（同时存在 $d$ 种解 $b$ ）

于是有
$R(n) = \sum _{d\mid n, \gcd(d, n/d) = 1} d - n = \prod (p_k^{k_i}+1) - n$

回到原问题。一个重要的事实是 $n^4 + 4 = ((n-1)^2 + 1)((n+1)^2 + 1)$ ，于是我们只需要考虑形如 $m^2 + 1$ 数的答案。

还有一个亟待解决的问题是 $((n-1)^2 + 1)$ 与 $((n+1)^2 + 1)$ 之间的公因子。
$\gcd((n-1)^2 + 1, (n+1)^2 + 1) = \gcd(n^2-2n+2, 4n)$
显然当 $n$ 为偶数时，会存在公因子 $2$ ，而没有公因子 $4$ 。

又 $n^2-2n+2 \equiv 2 \pmod n$ ，考虑 $n$ 大于 $2$ 的因子 $u$ ，则必定有 $u \not \mid n^2-2n+2$ 。

因而 $n$ 为偶数时， $\gcd$ 为 $2$ ，否则 $\gcd$ 为 $1$ 。

接下来，我们考虑使用筛法来求出所有的 $R(m^2 + 1)$ 。在这里，推荐 ZhouYuChen 的高效筛法，复杂度可以做到 $O(n \log \log n + n \log n)$ （由于去除的质因子非常大，所以实际非常不满）。

注意到 $m^2 \equiv -1 \pmod p$ ，在模 $p$ 意义下至多存在两个解 $m_0, p-m_0$ ，逐个去筛 $kp-m_0, kp+m_0$ 即可。但是，如何说明处理到第 $i$ 个数时，剩下的 $n$ 为质数？

proof

假设当前去筛的数为 $n = p_1 p_2 \cdots$ ，任取两个质因子 $p, q\ (p \le q)$ 。

需要说明的是， $n$ 不存在平方因子。因为 $n \mid m^2 + 1$ ，而显然 $m^2 + 1$ 不被任何质数的平方整除。可以得到 $p < q$

于是有
$m^2 + 1 \equiv 0 \pmod p \\ m^2 + 1 \equiv 0 \pmod q$

注意到，此时必定有 $m < \frac p 2$ ，也即 $m^2 + 1 \le \frac {p^2} 4$

假设
$m^2 + 1 = ap \quad (a \ge 1) \\ m^2 + 1 = bq \quad (b \ge 1)$
可以得到 $ap = bq$ ，根据 $\gcd(p, q) = 1$ ，那么有 $a \ge q$ 。得到 $m^2 + 1 \ge pq$ ，与上述式子矛盾！

于是就解决了整个问题。

Project Euler 口胡记录

Solutions

Hardest

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读