Project Euler 口胡记录

看不懂

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$ ，与上述式子矛盾！

于是就解决了整个问题。

最后编辑于：2018.09.02 18:59:54

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 217,826评论 6赞 506
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,968评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,234评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,562评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,611评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,482评论 1赞 302
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,271评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,166评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,608评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,814评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,926评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,644评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,249评论 3赞 329
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,866评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,991评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,063评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,871评论 2赞 354

Project Euler 口胡记录

Solutions

Hardest

推荐阅读更多精彩内容