Volume 03

101. Optimum polynomial

最多枚举到, 多项值插值一下.

102. Triangle containment

利用叉积判断即可.

103. Special subset sums: optimum

根据题目的信息, 我们可以利用构造出这一组非最优解, 猜测最优解每项的上面这个解的差不会太大, 取差不多就可以算出答案了, 好吧其实就是构造出来的解.

104. Pandigital Fibonacci ends

考虑到, 于是. 考虑这个数的小数部分, 可以得出就是的前位. 于是暴力枚举即可.

105. Special subset sums: testing

把集合大小相同的一起排序, 然后依次枚举相邻两个数判断大小即可.

106. Special subset sums: meta-testing

简单的可以知道集合大小相同且不相交的集合对有. 对于集合大小为的, 我们考虑哪些是不需要比较的. 不妨令在集合的元素为(, 在集合的为), 那么只有那些长度为的匹配括号是不需要比较的, 因为匹配, 所以可以找到一种匹配方案使得中每个元素都大于中每个元素. 匹配括号数目就是Catalan数. 于是答案就是.

107. Minimal network

直接跑prim算法即可.

108. Diophantine reciprocals I

做些化简可以的得到, 于是解的个数只和的约数有关. 考虑, 那么约数个数为. 暴力枚举计算即可.

109. Darts

注意到可以有S, D, T, 只能有S和D, 只能有S. 暴力枚举每种组合即可.

110. Diophantine reciprocals II

类比#108的结论, 然后观察一下可以知道. 写个爆搜就好了.

111. Primes with runs

通过factor命令可以尝试出, 于是直接暴力枚举未确定的位置然后判断是不是素数就好了.

112. Bouncy numbers

答案不是很大, 从小到大枚举计算就好了. 当然由于这个东西是单调递增的, 可以考虑二分答案, 然后数位dp计算.

113. Non-bouncy numbers

直接数位dp就好了, 记得减去全部位数相同的那些, 这个会多算一次.

114. Counting block combinations I

枚举红色的个数, 以及块数, 那么答案就是, 其中.

115. Counting block combinations II

考虑#114中的式子, 从小到大枚举即可.

116. Red, green or blue tiles

令, 那么答案就是.

117. Red, green, and blue tiles

枚举红绿蓝用的块数分别是 , 对答案的贡献是.

118. Pandigital prime sets

枚举每个子集, 计算出这个子集能够搞出多少种不同的素数. 之后枚举整数划分, 利用之前的结果计数即可.

119. Digit power sum

枚举所有的 即可.

120. Square remainders

考虑二项式展开, 那些项都是可以忽略的, 那么只需要考虑, 如果是偶数答案是, 如果是奇数答案是, 从枚举到即可.

121. Disc game prize fund

假设赢的概率是, 设置的奖金为, 那么为了不赔钱, 需要满足, 得到. 于是$x$的值应该取. 考虑计算概率, 令表示玩了轮, 蓝色球总共取了次的概率, 显然有. 用long long模拟下分数类就好了.

122. Efficient exponentiation

枚举每个, 爆搜即可.

123. Prime square remainders

同#120, 只有为奇数是有用的, 然后可以观察到的范围大概是左右, 筛出附近的素数判断下即可.

124. Ordered radicals

可以直接用筛法求出来, 排个序直接算答案就好了.

125. Palindromic sums

完全平方数只有个, 于是连续和最多只有个, 暴力枚举这些和然后判断是不是回文数, 记得去重即可.

126. Cuboid layers

找找规律可以发现一个的cuboid包了第层需要的cube数目为. 猜个上限, 暴力枚举使得不超过这个上限即可.

127. abc-hits

先用#124的方法求出所有的, 然后将排个序. 由于任意两个数互质, 显然. 考虑枚举, 然后根据从小到大枚举, 显然有, 不满足的直接break就好了. 然后算出检查下是否互质, 以及是否小于确定合法的.

128. Hexagonal tile differences

考虑每一圈的六边形边界, 可以通过简单的观察知道只有这些六边形的起点和终点才可能成为答案. 于是暴力枚举这些值, 判断是否满足条件即可.

129. Repunit divisibility

考虑到, 于是可以令开始枚举, 然后很快就出答案了.

130. Composites with prime repunit property

暴力枚举答案即可.

131. Prime cube partnership

猜测了下一定要是一个立方数, 并且也要是一个立方数, 然后显然会是一个立方数. 考虑, 可以得到. 由于是素数, 显然, 于是. 暴力枚举, 判断是不是素数就好了.

132. Large repunit factors

, 考虑的情况, 有, 可以得到. 于是从小到大枚举每个素数判断即可.

133. Repunit nonfactors

利用#132的结论, 暴力枚举每个素数, 然后从枚举到（应该可以更少, 知道找到循环节为止）, 判断是否存在满足.

134. Prime pair connection

可以列出式子, 这是个同余方程, 直接解就好了.

135. Same differences

令, , 于是是的约数, 暴力枚举的约数判断是不是的倍数即可算出方程解数.

136. Singleton difference

同上, 枚举约数的时候不要特别暴力即可.

137. Fibonacci golden nuggets

可以求出, 令, 化简下得到, 根据求根公式, 可以得到. 要令是有理数, 那么是整数. 暴力枚举找规律之后可以发现第个golden nugget是.

138. Special isosceles triangles

令, 根据, 以及可以得到. 参考Dario Alpern’s Generic Two integer variable equation solver, 可以得出:

139. Pythagorean tiles

考虑勾股数为, 那么只要满足就是合法的答案. 于是只要枚举所有互素勾股数就好了, 参考Tree of primitive Pythagorean triples即可.

140. Modified Fibonacci golden nuggets

可以求出, 类似#137, 令, 化简得到, 只要是完全平方即可, 考虑这个不定方程, 同#138, 参考Dario Alpern’s Generic Two integer variable equation solver, 可以得到如下递推式子:

141. Investigating progressive numbers, , which are also square

不妨令, 令公比为, 那么有.

令. 那么有. 考虑到, 那么必有. 可以令, 那么, , 于是可以得到. 暴力枚举所有可行的, 然后判断是不是完全平方数即可.

142. Perfect Square Collection

考虑枚举, 然后解出, 判断剩下的数是不是完全平方数即可.

143. Investigating the Torricelli point of a triangle

通过简单的推导, 可以知道那三个角都是, 根据余弦定理, 可以得到和的关系, , .

考虑构建这样一个图, 枚举所有可行的使得是完全平方数, 在和之间连一条无向边. 那么只要找到图中的一个三元环就找到了一组合法的解. 按照度数连边, 三元环可以.

为了快速枚举所有可行的, 可以参考Finding parametric equations for 120 and 60 degree triples.

构成了一个的三角形(即), 当且仅当存在两个互质的正整数和 使得:

144. Investigating multiple reflections of a laser beam

推出反射的公式, 然后暴力迭代直到出去为止.

145. How many reversible numbers are there below one-billion?

可以直接暴力枚举每个数, 判断是不是reversible number.

146. Investigating a Prime Pattern

通过同余分析可以知道, , , , , , . 先根据上面条件筛掉不合法的数, 之后用Miller–Rabin primality test判断即可.

147. Rectangles in cross-hatched grids

对于非斜着的只需要枚举子矩形的大小为, 出现次数为, 考虑那些斜着的, 枚举最下面那个顶点的为止, 考虑每次斜着往左扩展后, 斜着往右最多能扩展多少即可.

148. Exploring Pascal's triangle

考虑lucas定理, 不被整除, 当且仅当在进制下不会产生进位, 也就是说令在进制下为, 那么都成立, 于是对着数位dp就好了.

149. Searching for a maximum-sum subsequence

暴力个方向, 用最大字段和的搞搞.

150. Searching a triangular array for a sub-triangle having minimum-sum

暴力枚举即可.