2021, 2022 年电子科技大学 ICPC 暑假前集训数学与几何专题部分题解

只有部分题解，完整题解实在太多了，写不过来了（主要是不会）……

排序主要按难度和相关性，并没有按时间顺序和题号顺序排。

以下多组数据题目的时间复杂度均标注的是单组数据的时间复杂度。

黑灰游戏

题目描述

个石子从左到右排成一排，两人每人每次从左右两端中的某一端恰好拿走 个石子，拿不走 个石子的话游戏停止。拿走石子数多者胜。问最后谁会胜利。

数据范围：。

题解

如果 是奇数，则 Kate 获胜，否则二人平局。因为这个游戏与从左取，从右取还是任意取黑灰是无关的，无论先后手状态都是确定的。如果 是奇数，则先手会比后手多拿一轮 个石子，偶数的话两人拿的轮数是一样多的。

来自 Codeforces Round #425 (Div. 2) A. Sasha and Sticks。

时间复杂度：，空间复杂度：。

代码见这里

黑灰游戏 · 改

题目描述

堆石子从左到右排成一排，第 堆石子有 个。令轮数从 开始增加，游戏按如下步骤进行：

• 奇数轮由 Kate 指定一堆非空的石子堆开始。然后 Emilico 从这堆石子中拿走至少一个石子。
• 偶数轮由 Emilico 指定一堆非空的黑灰堆开始。然后 Kate 从这堆石子中拿走至少一个石子。

取走最后一个石子的一方获胜。两人均使用最优策略，请判断 Emilico 在这场游戏中是否一定可以获胜？

数据范围：。

题解

设：

• 为只有一个石子的石子堆数；
• 为石子个数严格大于 的石子堆数；
• 为现在指定的石子堆的石子个数。

如果 ，那么当且仅当 为奇数时我们才会获胜，否则必败。这是显然的，因为我们只有当 为奇数时才会取走最后一个石子。

下面讨论 的情况，我们可以将指定堆后的状态分为如下三种情况：

• （W 态） 是偶数；
• （L 态） 是奇数且 ；
• （O 态） 是奇数且 。

下面我们将说明，只有 L 态是必败态，而 W 态和 O 态都是必胜态。

当 是偶数时，如果 ，我们总可以移除这个石子，然后指定另一个仅有一个石子的石子堆让对方取，因为 是偶数，并且 ，所以 ，我们总可以找到这样的石子堆，这样就引导对方进入了 L 态。

如果 且 ，那么我们可以直接取走指定的石子堆中所有石子，这样对方就进入了 且 为偶数的必败态。

如果 且 ，我们可以取走指定堆中 个石子，也就是剩一个石子，并且指定这个石子让对方取走，这样对方也进入了 L 态。

当 是奇数且 时，对方总会进入 W 态。

当 是奇数且 时，如果 ，我们可以取走指定堆中 个石子，这样 就变为了偶数，，对方就进入了必败态。如果 ，我们可以取走指定堆的所有石子，并指定一堆只有一个石子的石子堆，因为 是奇数，所以这样的石子堆一定存在。因此对方一定会进入一个 L 态或必败态。

每个 W 态或 O 态都会引导对方进入 L 态或者 的一些必败态，而每个 L 态总会让对方进入 W 态。在每次转移时，石子总数均减小。因此，所有的 W 态或 O 态都是必胜态，所有 L 态都是必败态。

因此，先根据 是否等于 讨论后，再根据 的奇偶性讨论均可。由于 Kate 总采用最优策略，因此最开始时，如果可以让 Emilico 为 L 态，Kate 总会让她为 L 态。

改编自 CEOI 2021 Day2 T1。原题是一个交互，要求模拟这个过程。

时间复杂度：，空间复杂度：。

代码见这里

Kanade Hates Modular Multiplicative Inverse

题目描述

给定 ，求

的一组最小解 ，满足 最小的同时 。

数据范围：，保证 是一个质数。

题解

不妨考虑

这一方程，其中 为一个自然数。

由于 ，则有 。化简一下

注意到 ，我们要让 和 都最小，那么 也要最小。下面这个问题就变成了求一个分子和分母最小的分数，使得这个分数在两有理数之间，这个问题就可以用 Stern-Brocot 树解决了。

还有一个更简单一些的做法，复杂度和 Stern-Brocot 树相同。

来自：HDU 6624. fraction

时间复杂度：，空间复杂度：。

代码见这里

Rust

题目描述

有一 阶多项式

对于给定正整数 ，求

的值，对 取模。

数据范围：。

题解

先对式子变一下形

后半部分 的求值实际上是一个板子，可以在 的时间复杂度下求值，其中 为 的指数部分。

这个板子实际上不想讲，主要是从多项式角度推的，但是我不会。详细推导过程可以看这篇日语博客。Min25 的博客关了，悲。

我们下面介绍一种会二项式定理就能推的方法。令 。

现在我们不想要这个 （因为太大了），希望把计算的复杂度下降到 的（因为不大），那么我们可以考虑去隐藏 这个细节。所以我们把这个求和看成一个整体（也就是一个多项式），通过某种方法把它解出来。那么我们需要在右边把 构造出来，我们考虑稍微变个形。

上一步化简中，由于 ，所以 ，但 ，所以需要保留上述形式。

我们扰动了一下 ，是因为我们希望用二项式定理提出来 ，并且隐藏 ，构造 。

接着化简

我们看到后面的部分大概就像一个 了，但是多了一个 ，那么我们提出来

容易发现，对于 的求和最后一项就是 了，但是这里我们形式化一点，因为将 从和式中抽出来，会使求和范围变为 到 ，而当 时，这个范围是不规范的，所以我们单独讨论一下 。

实际上，当 时，，实际上是一个等比数列求和的形式。只需特殊考虑一下公比 的情况，其余情况均可使用公式求出答案。

下面我们只考虑 时，那么 可以进一步化简

这里我们需要把 除到等号右边，就能获得 的一个递推式了，但是 时等号左边就变成 了，我们仍需讨论 的情况。

实际上， 时，，这是一个求自然数幂和问题，可以参考这篇知乎回答。

那么我们考虑 时，直接除到右边

这样，我们就可以在 的时间复杂度下递推出 到 范围内所有的 了，之后乘系数求和即可。请注意整个过程中只需要使用一次快速幂求出 的值，并不需要用快速幂求 的值，因为递推的时候就可以 计算了。

求组合数也不需要杨辉三角，只需要 求一下阶乘和逆元的阶乘即可。如果模合数的话就需要使用杨辉三角了。

事实上，这个时间复杂度与使用上文提到的多项式板子的时间复杂度相同。

加强自 2017 年清华大学研究生招生计算机类上机考试 - 多项式求和。

时间复杂度：，空间复杂度：。

代码见这里

天结

题目描述

对于两个计数器，每次先从 等概率随机选择一个整数，如果这个数不是 ，则先给第一个计数器加一，记目前第一个计数器的值为 ，然后给第二个计数器加 。问这个过程进行 次后，第二个计数器的值的期望，乘 后模 输出。

数据范围：。

题解

令 ，则

对概率化简

而 ，则

实际上，所求答案为

注意到有

代入得

只考虑前半部分式子，注意到 ，代入之

分两部分考虑后面的和式，当 时要减去 时的值，也就是 。

当 时

前面部分可以直接二项式定理逆用，后边考虑 后再用二项式定理

那么合起来

注意到我们需要求的第二类 Stirling 数 ，于是需要使用 NTT 加速计算。

时间复杂度：，空间复杂度：。

代码见这里

新月之舞

题目描述

求

数据范围：。

题解

我们分两段考虑

单独考虑后面的和式

对于 的部分，接着展开。

反向考虑 对答案的贡献，对于 中的正整数，有 个整数有 这个因子，每个整数对于答案的贡献为 ，所以有

接着考虑 的部分。

接着考虑枚举 ，类似地，对于 中的正整数，有 个整数有 这个因子，每个整数对于答案的贡献为 ，我们考虑使用 这样的方式来枚举这 个整数，其中 ，则有

其中 ，注意上式中的变形。

让我们把 捏起来。

使用数论分块求解即可。

求解时需注意除法能否整除，可以把后两项合并起来求和，就可以避免除 2 时的整数与否的判断了。因为答案级别是 的，因此需要使用 __int128。

来自 UOJ 群友某天问的一道题。

时间复杂度：，空间复杂度：。

代码见这里

Жизнь по кругу

题目描述

现有一个半径为 的圆，问圆上整点数个数。

数据范围：。

题解

结论是，设 ，其中 为圆的半径， 为 的唯一分解。则答案为

证明见 3B1B 的视频。

于是用 Pollard rho 分解质因数即可。

加强自 HAOI 2008. 圆上的整点

时间复杂度：，空间复杂度：。

代码见这里

利兹与青鸟

题目描述

求

和

的值。

数据范围：。

题解

这道题涉及一些复分析方面的知识，但不超过学了 FFT 的复分析知识范围。

对于求 的过程，已有研究 [1]，可知 。

下面考虑求 的过程。

则

令 ，则

我们来考虑

不妨设现在要求的是

最终答案就是

了。

我们猜测

也可以简写为

在 的情况都符合（实在不行打个表系列）。下面考虑证明之。

考虑 Möbius 反演的一个补充结论

这里考虑 可知，详细过程可参考 莫比乌斯反演 - OI Wiki。代入之

考虑如何变换交换和号，由于 ，考虑 ，则可以把上式改写为

则可提取与化简为

不妨设

则所求为

实际上，对于 的求和是一个经典复分析问题，结论为

我们对其的证明放在最后。则根据其结论可化简 。

我们就这样证明了上述猜测的正确性。

那么答案就是

其中 是 A023900，等于

其中 表示 的质因数分解中的质数。

和 的求和是 rockdu 证的。

可以在 的复杂度进行质因子分解，众所周知 ，之后对于这些质因子分别计算，代价为 。但当 时，，因此统计答案时间代价可忽略不计。使用 的分解方法是无法通过的，第 4, 5 两组数据都是大质数。

因为整个不除以 的部分可能会占用 位（因为带符号），因此直接用 double 的话将引入精度误差（即使除以 是无误差的，但将 long long 转成 double 的时候精度误差就存在了），可以使用 long double 解决，或者写无精度误差的方法（但是要注意 C++ 对于负数除法并非向 舍入，需要转为绝对值）。

The Art of Shaving Logs.

来自 OI Wiki 群友问的问题（大概 4 月份？），当时没人回答。

时间复杂度：，空间复杂度：。

实际上本题仍可以将 的范围出到 ，并使用 Pollard rho 算法解决。但考虑到编码的困难和可以预见的数据类型使用问题，故作罢（ 大概是 级的）。

附录一：证明 ，也就是证明

下面记 为 次单位根，我们实际上求的就是

的实部。

我们考虑上式为等差乘等比，高考题之

上下两式作差

实际上前面的求和部分是一个 到 次单位根求和，当 时，有

上式从复分析角度可知。

那么

请注意，，当 时 前的系数为 ，不能简单相除。可以直接计算 时的结果为 。

当 时，。再次根据复分析知识，，则 。请注意 是一个实数，因此对于单位根的计算我们取实部。

由此， 已被证明。

下面简单介绍需要的复分析知识（十分不严谨，仅供参考），如果已经学习过 FFT 或相关知识可以跳过。

根据 Taylor 展开可知

这就是 Euler 公式。根据此公式有

我们实际上就解出了所谓的「 次单位根」

我们首先来证明 时

我们考虑 Euler 公式

那么实部就是 。

关于 的前 项和，直接使用等比数列求和公式即可。注意 。

附录二：如何猜答案

先写个暴力打 的表，关于 ，建议把 表背下来。

对于 ，首先我们考虑观察这些值有正负，还有 和 的值，首先考虑将它们都乘 。乘完 之后发现好像这些值越来越大，可以考虑猜一个 ，然后对这些值都除 。首先观察所有质数位置，都等于 ，然后考虑观察 ，其中 都是质数的位置，我们考虑分解一下，发现没有什么卵用，但是考虑 之后都能拆成 ，我们就猜它分解之后 乘起来，加 乘 除 。然后就猜出来了。

代码见这里

Violet mag Veilchen

题目描述

有一个半径为 的圆，求圆内（包括圆上）整点数。

数据范围：。

题解

In memory of Min25.

这里也有一些粗略的介绍。

一个很有意思的结论是，圆内（包括圆上）所有整数点形成的凸包规模并不大。究其原因，是因为函数较为平滑，考虑圆在第一象限内的图象，其二阶导的绝对值小于 的范围很大（具体有多大呢，留作课后作业后面再说）。实际上，圆内（包括圆上）所有整数点形成的凸包规模为 。其中 为圆的半径。

首先圆有很好的对称性，在这里我们仅考虑圆域位于第一象限的部分。最终答案就是第一象限的部分的答案乘 。再根据第一象限的圆域是以 为轴对称的，所以考虑答案实际上是一个八分之一圆内的答案乘 （当然还要处理一些边界问题）。

我们设 是凸包的一个顶点，并且只考虑圆域位于第一象限且在 与 轴之间的部分，下面我们要按顺时针方向找凸包的下一个顶点 。

根据单调性，有 且 。并且 应该是大于 且满足条件的最小值，对于 也是同理的。这样才能满足是下一个顶点。这样考虑很难下手，因为并没有用到凸包性质，所以我们转而考虑斜率。

因为都是凸包上都是整数点，所以对于凸包的任何边，其斜率都是有理数。不妨设

我们的目的是求这样的一组 满足上述条件。可以使用 Stern-Brocot 树，并可以发现这个过程和在树上二分挺像的。因为我们每次计算的中间值是 ，由于 Stern-Brocot 树的性质，会保证这个分数是最简的，所以有 这样的性质。

为了统计方便，因为我们要算的圆域是闭区域，我们需要把圆周也包括进来，所以考虑的凸包是能够完整覆盖这个圆的最小整点凸包。不妨设 ，引入圆和凸包性质分情况讨论。

如果 ，则令 继续讨论。这里是递归到的值不在圆外的情况，表示斜率的相反数仍可以减小（理解上来说，就是现在凸包上的边太竖直了，减小后让他不那么竖直，保证下个点仍在圆外）。

如果 ，则需要讨论：

• ，则下一个点就可以确定为 ，因为这样的话下一个点处圆的切线斜率更大，可以保证下一个点的下个点一定可以在圆外，从树的性质来说又可以保证满足要求，因此可以确定；
• 否则，就表示凸包边的斜率大于切线处斜率。根据圆的一阶导和凸包性质，下一个点就会在圆内，所以扩大斜率的相反数，即 。

由于凸包的边的斜率是单调的，所以考虑用栈将每次递归到的分数存起来，就可以达到理想的复杂度了。

最前面有个问题，圆在第一象限内的部分二阶导绝对值小于 的范围有多大。实际上是一道微积分 MATLAB 题，下面放一段过程，如果有问题就凑合看吧……

可知

易得 在研究定义域 恒成立。

我们实际要解

分母恒正，移项，两边平方，去括号，移项，化为多项式，然后丢 MATLAB 解出来（考虑实根即可）

（实际上令 就是三次方程了）

考虑不等号左边的单调性，可得范围为

易知 ，证明留作课后作业。

时间复杂度：，空间复杂度：。

代码见这里

模拟人生 2077

题目描述

平面上 个点，求由这 个点组成面积最大和面积最小的三角形面积。

数据范围：。

题解

对于求最大三角形，直接旋转卡壳即可。

对于求最小三角形，极角序是错的。这个方法以每个点为原点做点的极角序，统计极角序相邻的两个与原点形成三角形的面积取最小值。但需要注意最小三角形并不一定出现在极角序相邻的两个点，还需要考虑极径长度。

对于求最小三角形，考虑枚举每一条线段，用离这个线段最近的两个点更新答案。那么现在只有点到线段的距离有用了，考虑对线段按斜率排序，这里也可以利用极角序。对于排完序后的线段，因为现在只有点到线段的距离是我们需要考虑的，只要线段之间的相对位置不变即可。

考虑一种排序方式为按从 轴负半轴到正半轴逆时针排序，将点按横坐标从小到大排序。我们枚举一条线段 ，表示由点 和点 组成的线段。根据上面的排序方式，我们只需要考虑点 的前一个点和点 的后一个点即可。其中一个事实是 和 一定是顺序上相邻的。切换到下一条线段时，按照排序后的序列，只有 和 对于下一条线段的相对位置变化了。交换两者的顺序即可。维护两个序列，一个表示某个点的位置，一个表示某个位置的点即可维护这样相邻交换的问题。

时间复杂度：，空间复杂度：。

代码见这里