又一道 GCD 问题 题目链接：nowcoder 213804 到主站看：https://blog.csdn.net/weixin_43346722/article/details/112740731 题目大意 给你一个数组，要你求出从他们中选出 个的 gcd 的最大值。 思路 看到这道题，我们考虑看有多少个数有 这个因子，设其为 。 那我们分解一下质因子（用素数筛选法和 floor(sqrt()) 来加速），然后 dfs 一下，就可以得到一个数的每个因子，就从而求出了 。 那有了这个，我们可以求出要选出 个数的 gcd 最大值是多少了。（就是从后往前搜第一个 大于等于 的数） 那我们可以先弄...

一道GCD问题 题目链接：nowcoder 213804 到主站看：https://blog.csdn.net/weixin_43346722/article/details/112734928 题目大意 有一堆数，你要把他们都加一个尽可能小的数 k，让它们的 gcd 尽可能大。要你输出这个 k 和最后最大的 gcd。 思路 这道题让所有数都加一个数，那他们任意两个数的差都是一样的。 那我们再看看 gcd，如果一堆数的 gcd 是 x，那任意两个数的差的绝对值一定是 x 的倍数。 那我们不如求出这些数排序后，每两个数之间的差组合成一个新的序列，这个序列的 gcd 就是它们可以有的最大的 gcd...

减数游戏 题目链接：nowcoder 214272 到主站看：https://blog.csdn.net/weixin_43346722/article/details/112730284 题目大意 有一个序列，你每次可以把两个数去掉，改成这两个数的乘积加 k。然后问你变换到最后剩下的数最大可以是多少。 思路 这道题我们考虑贪心，可以看出肯定是选择最小的那两个乘。 那我们考虑用堆维护，但是你会发现乘到后面会有取模，然后就会导致堆里面最小的并不是真正最小的。 那怎么办呢？那我们会发现，乘到最后，数已经很大了，把最小的两个乘起来，也会比之前最大的还要大。 那我们就考虑先用堆乘到这个情况（就先不取模...

小D和他的魔法石 题目链接：nowcoder 214271 到主站看：https://blog.csdn.net/weixin_43346722/article/details/112727063 题目大意 有一些魔法石，每种有无限个，用一个耗费一个值的体力，获得一个值的能力。 然后你可以有 k 次机会把两种魔法石的体力值互换，一定要把 k 次都用完。 然后问你在耗费体力不大于 m 的时候，最多能有多少能力值。 思路 这道题主要是考虑分类讨论。 首先，很明显的就是如果 ，我们就直接做完全背包。 那考虑有换的机会，我们可以想到贪心。让一个魔法石耗费体力值最小，获得能力值最大。 那考虑怎么才能换出...

广义肥波 题目链接：nowcoder 214267 到主站看：https://blog.csdn.net/weixin_43346722/article/details/112726718 题目大意 定义广义斐波那契数列： 然后让你求  思路 看到题目的范围，我们可以看出应该是枚举一个 ，然后其他数的 log，大概这样的复杂度。 然后很明显枚举 可以得出 ，但是你要求的是 ， 不能取模，你总不能搞高精吧。 那我们考虑不求 ，枚举 求出 的值 。那我们可以看出转移就是：。（就是全部运算往上诺一级） 这样就可以在取模的意义下进行而不出问题了。 代码 #include<queue> #i...