Volume 06

251 Cardano Triplets

两边同时立方, 然后化简可以得到, 令, 那么有. 于是可以想到一个暴力的方法: 枚举, 然后对分解质因数, 这样就可以得到所有的了. 这样比较慢, 大概需要几分钟吧.

令, 那么, 于是式子可以化简为, 由于, 那么可以表示为, 于是进一步化简得到, 其中.

于是就可以考虑枚举使得并且. 不妨枚举(显然是奇数, 是偶数), 如果找到了的一组最小解, 那么其他解要满足. 于是只要找到符合条件的就好了. 由于, 显然都是, 可以直接暴力枚举, 可以用扩展欧几里得算法求. 这样大概能在s内出解.

252 Convex Holes

这个就是最大空凸包. 枚举所有最大空凸包的最低最左点. 对于每个枚举到的点, 先将上方的点按照极角排好序. 令表示满足下面条件的最大凸包: 在凸包上顺时针过来的第一个点是, 并且顺时针过来第一个点不在的左手域, 可以等于. 这样复杂度可以做到.

253 Tidying up

考虑加完点后, 每个联通分量的大小, 显然只需要考虑这些大小构成的multiset就好了. 于是就可以用这个作为状态进行dp, 同时记录当前的联通块数目, 实际上还需要加入最左边和最右边两个联通分量的大小.

254 Sums of Digit Factorials

注意到, 如果, 显然就足够表示了, 于是这部分可以直接暴力. 那么当的时候, 可以证明, 一定是这种形式, 其中, 的个数为. 那么, 现在问题是知道了的值, 如何快速求出最小的. 这个只要用阶乘进制来表示就好了, 先用, 然后, 直接贪心即可.

255 Rounded Square Roots

可以猜测到, 显然可以把划分成若干个小区间, 小区间内每个数需要的次数是一样的.

根据, 可以得到, 于是可以得到的范围是.

根据上面的式子, 对区间进行分治就好了.

256 Tatami-Free Rooms

可以在oeis上搜到Tatami-Free Tiling的方案数是A068920, 上面给出了一个链接, 从这个链接里可以获得如何快速计算是不是Tatami-Free. 于是暴力枚举每个数, 然后枚举约数判断就好了. 一个优化是这个数约数个数要至少是个, 通过线性筛预处理, 可以少枚举很多.

Counting Fixed-Height Tatami Tilings这篇paper似乎提供了一些更加有趣的性质, 有空可以研究下.

257 Angular Bisectors

根据角平分线定理, 可以得出. 显然可以得出.

当的时候, 显然, 答案为.

当的时候, 可以算出, 其中.

当的时候, 分成两种情况:

, 其中.
, 其中.

于是用Stern-Brocot Tree枚举互质的即可.

258 A lagged Fibonacci sequence

直接套用的线性递推即可. 原理解释Cayley–Hamilton theorem.

259 Reachable Numbers

就是一个爆搜. 令表示只用到这些数字能构成的结果集合. 枚举中间的分界点, 暴力合并和即可.

260 Stone Game

直接暴力dp就可以过掉这个题了, 令表示这个状态是否必胜, 然后枚举种转移, 暴力转移. 结果用bitset存就可以存下了.

261 Pivotal Square Sums

化简下式子可以得到, 令, 于是有, 这个是一个pell方程, 只要找出了所有的基础解, 就可以用递推式了.

求基础解没有找到什么好方法, 只能暴力. 考虑, 那么稍微化简下可以得到, 也就是说, 其中. 于是可以根据这个暴力枚举, 然后检查是否存在就可以找出所有的基础解.

262 Mountain Range

显然, 这个函数是关于平面对称的. 然后用Mathematica画出这个函数的图像, 可以发现在和两个平面处是瓶颈, 通过二分或者三分可以求出这两个最高点是和, 于是.

再次使用Mathematica画图, 可以观察到, 最短距离显然是从到达曲线的某个点, 然后从沿着曲线到达点, 最后从直接到, 其中和是两条切线. 通过二分可以求出这两个切点分别是.

直线距离直接计算就好了, 剩下来的曲线部分可以考虑定步长simpson, 枚举, 用二分确定出, 算下相邻两部之间的距离, 求个和就好了.

263 An engineers' dream come true

首先可以从wiki找到如何判定Practical number: 令 , 那么是practical number当且仅当, 对于所有都有, , 并且是偶数, 也就是.

暴力显然比较慢, 考虑利用整除性分析的性质.

由于是素数, 那么显然不能是的倍数, 不妨令. 那么是的倍数, 不是的倍数. 如果, 那么不是的倍数, 是的倍数.
由于是practical number, 于是要是的倍数, 也是的倍数.
由于都是素数, 那么一定是的倍数. 不是的倍数.
同样由于都是素数, 一定是模余或者.
由于是practical number, 那么要是的倍数, 于是. 然后由于是practical number, 那么要是的倍数. 所以可以得到.

综上可以知道或者. 于是暴力枚举, 检查是不是practical number以及素数就好了.

264 Triangle Centres

不妨令三个顶点坐标是, 那么可以知道. 然后由于这三个点都在圆周上, 有. 消去, 可以得到下面这个方程:

考虑枚举, 可以直接解出, 然后其他数也可以解出来了, 直接判断合法性就好了.

265 Binary Circles

直接爆搜每个位置是0还是1, 然后开个数组记录每个被访问数即可.

266 Pseudo Square Root

以内的素数只有个, 考虑折半枚举, 分别枚举每个素数乘还是不乘, 把结果取对数后用double存储. 然后排序后, 用双指针或者二分都可以.

267 Billionaire

猜测了下这个概率是可以三分的. 假设有次硬币向上, 那么收益是, 也就是要, 取对数得到. 显然要使概率最大, 只要使最小即可, 于是根据进行三分即可.

268 Counting numbers with at least four distinct prime factors less than

首先可以容斥计算出至少被以内一个质数整除的个数. 然后减去只被,, 个整除的个数即可. 这些同样可以枚举质数, 然后进行容斥, 可是这样跑的很慢呢. 考虑如何才能同时进行容斥. 只要算出系数, 就可以只用一边容斥就好了. 于是可以先通过一次dfs算出每一个容斥项的系数, 然后再容斥计算既可.

269 Polynomials with at least one integer root

根据Rational root theorem, 可以知道根一定是的约数. 如果每个多项式只有一个整数根, 那么就直接计算就好了. 如果有多个可以考虑用容斥原理来计算.

对于给定的一些根, 如何快速计算多项式数目呢? 第一种方法是考虑折半枚举, 分成前后各位, 的复杂度还是可以接受的, 大概几分钟就计算出来了. 另一种方法是考虑dp. 不妨假设只有一个根, 那么可以表示为, 算出合法的数目, 那么的数目也是知道的. 那么只要枚举的系数, 用多项式乘法计算出的系数就好了. 计算过程中要求的系数一直小于, 这个就可以数位dp做了. 有多个根的话, 在dp数组上多开几个维度就好了.

270 Cutting Squares

和普通的凸包三角剖分计数一样, 直接固定一条边, 然后枚举另一个三角顶点的位置就好了. 当割出一条斜边之后, 那么就可以直接拿这条斜边当固定的边, 计算会方便很多.

271 Modular Cubes, part 1

分解后可以知道. 考虑的解, 我们可以找出一些只有唯一解的那些, 有, 显然可行的需要满足, 于是暴力枚举即可.

272 Modular Cubes, part 2

如果把算进去, 那么其实是一个积性函数, 令, 那么. 根据Cubic reciprocity的一些性质, 可以知道, , 其余素数幂次都是.

考虑到, 我们需要个满足的素数. 最小的个满足的素数是, 算了一下其他素数的上限是. 于是找出以内的素数, 进行爆搜就好了(加一些可行性剪枝后跑的飞快).

273 Sum of Squares

首先处理出每个素数, 显然这个是唯一分解的. 然后考虑用来合并就好了. 由于以内满足条件的素数不太多, 直接暴力合并就好了. 如果素数变得更多, 可以考虑用折半枚举的方法来合并.

274 Divisibility Multipliers

答案就是, 其中表示模的逆元.

275 Balanced Sculptures

直接爆搜, 然后判断合法性. 可以用Redelmeier method来枚举polyominoes. 就是维护个集合, 分别表示polyomino里面的点, 候选点集, 以及不能被选上的点. 每次从中取出一个点, 可以扩展到或者中, 这样就可以不重不漏地枚举了.

276 Primitive Triangles

令表示周长为的整数边长三角形数目, 这个可以在oeis上找到公式. 令是互素的那些三角形个数, 那么显然有, 移个项得到, 递归计算即可.

277 A Modified Collatz sequence

令, 那么显然可以表示为, 也就是, 显然可以通过序列递推得到, 于是只要用扩展欧几里得解一个不定方程就好了.

278 Linear Combinations of Semiprimes

就是要求Frobenius number, 对于个数; 对于个数, , 如果.

题目中的数恰好满足条件, 于是.

279 Triangles with integral sides and an integral angle

那个角度只可能是, 和, 于是用之前题目的结论就好了.

280 Ant and seeds

马尔科夫链的一些知识. 令是概率转移矩阵, 其中第一行是吸收态(结束节点). 令, 那么的第一行和就是答案. 矩阵很大, 不好直接求逆. 考虑是一个全的列向量, 令, 那么就是我们要求的答案. 上面式子两边同乘以, 得到. 于是只要解个方程组就好了. 可以考虑用稳定双共轭梯度法进行迭代.

281 Pizza Toppings

可以得到公式, 当的时候需要特判下. 于是暴力枚举即可. 公式推导, 参考Necklaces with Fixed Density.

282 The Ackermann function

当的时候可以直接快速幂算出答案, 时答案显然是一样的, 考虑用来加速.

283 Integer sided triangles for which the area/perimeter ratio is integral

实现这篇paper Heronian Triangles Whose Areas Are Integer Multiples of Their Perimeters的算法就好了.

284 Steady Squares

参考这个Automorphic number会得到这个题的做法.

每个长度都最多只有个符合条件的数, 其中一个解满足, 另一个解满足. 并且, 除了个位(和为), 其他每一个位上数字之和都是.

285 Pythagorean odds

显然有, 化简之后可以得到合法的就是两个圆环在第一象限的面积, 直接计算就好了.

286 Scoring probabilities

显然是可以二分的, 于是只要二分答案, 然后通过dp计算出概率就好了.

287 Quadtree encoding (a simple compression algorithm)

维护正方形个顶点的颜色, 颜色相同可以直接返回, 否则分成4份递归计算.

288 An enormous factorial

直接根据阶乘的中质因子个数的公式计算就好了.

289 Eulerian Cycles

290 Digital Signature

直接数位dp就好了, 令表示搞到了第位, 后面的进位是, 的数字和减去的数字和是的方案数, 直接枚举当前位的数, 然后转移即可.

291 Panaitopol Primes

的形式是, 枚举, 测试是不是素数就好了. 证明如下:

令, 那么. 于是变成

由于和互质, , . 于是只有当时才可能是质数.

292 Pythagorean Polygons

首先枚举所有的三元组满足, 那么这些三元组可能构成凸包上的边. 考虑把这些边按照逆时针顺序排序(按照向量的方向). 那么凸包上的边一定是按照顺序取出若干条向量依次拼接而成的, 于是就可以考虑用dp来计算.

令表示用了前条线段, 从出发, 当前到了, 且现在边长和为. 转移的话就是枚举下一条选哪条线段, 注意为了能够组成凸包, 方向相同的线段需要一起处理. 最后答案就是, 其中表示总共有条线段. 记得还要减去只有两条边的凸包.

293 Pseudo-Fortunate Numbers

暴力枚举所有的admissible number, 然后暴力枚举即可. 的个数不是很多.

294 Sum of digits - experience #23

列出转移矩阵, 做矩阵快速幂即可.

295 Lenticular holes

考虑枚举两个交点构成的格点矩形的大小为 , 显然. 考虑对角线的方程是, 那么圆心显然在直线上, 于是可以知道和都是奇数. 接下来用扩展欧几里得算法可以求出合法的整点, 也就是圆心的位置. 由于内部不能有整点, 也就是说距离直线最近的整点不能在圆内, 这样就可以求出一系列合法的半径.

对于一条直线, 我们可以算出总的贡献, 但是这样是有重复的, 有些半径会在多个直线上出现. 通过简单的测试发现, 一个半径最多只会在条直线上出现, 于是考虑用容斥原理减去重复计算的答案.

296 Angular Bisector and Tangent

简单的推导可以知道. 令, 其中, 那么有, 显然要是的倍数, 令. 于是暴力枚举每个, 根据和可以列出一个关于和的线性规划方程组, 求出区域, 然后计算整点个数就好了.

297 Zeckendorf Representation

找个规律可以发现很明显的递归结构.

298 Selective Amnesia

考虑Robin的策略, 其实就是一个队列, 一直加在队尾, 长度超过后从队首拿掉. 于是所有数都以Robin的数为基准进行重标号. 使得Robin的数一直是. Larry那边, 如果有和Robin一样的数, 就按照Robin的标号, 否则新增一个新的标号. 例如: Robin是, Larry是, 那么可以重新标号为和.