算法

BSGS算法（baby step giant step，大步小步算法），又叫北上广深算法（不是），是一种基于中间相遇思想求解离散对数的算法，即求解类似于ax≡b(modm)a^x\equiv b\pmod max≡b(modm)的方程。 BSGS算法 首先介绍最普通的BSGS算法。普通的BSGS算法要求mmm和aaa要互质，既然互质，那么根据欧拉定理 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1\pmod m aφ(m)≡1(modm) 也就是说，ax(modm)a^x \pmod max(modm)以φ(m)\varphi(m)φ(m)为周期循环，那么如果方程有解，解一定在000到φ(m)\varphi(m)φ(m)之间，如果暴力枚举，当mmm为质数时φ(m)\varphi(m)φ(m)最大为m−1m-1m−1，最坏复杂度为O(m)O(m)O(m)。 普通的BSGS算法就是对上述暴力算法的一个优化，我们可以把xxx改成At−BAt - BAt−B，那么原式变成aAt−B≡b(modm)a^{At - B} \equiv b \pmod maAt−B≡b(m ...

原题链接 这题的思路其实很简单，就是直接贪心加暴力即可。有nnn个苹果和mmm个人，要想平均分配同时使切苹果的次数最少，那么就只需要切多出来的那部分就行了，也就是n mod mn \bmod mnmodm，其他的既然已经能够平均分配，切了之后也依然能平均分配，没必要画蛇添足地去切。所以只需要一个while循环就能解决： 12345int a = n % m;while (a) { ans += a; a = a * 2 % m;} 当然，如果直接这样写的话，就会发现样例都过不了。因为有些情况是无论怎么切都无法平均分配的，上述代码遇到这种情况显然会直接死循环，所以这题的关键就在于如何判断能否平均分配。 首先，假如某种情况下可以均分，比如每个人分到了1.5个苹果，那么我们就可以把那些重量为1的苹果都切成0.5，也就是切成最小的，同时苹果依然可以均分。这么做的意义在于，当我们把所有苹果都切成最小的那种时，其实就相当于在每一次切苹果时都是直接切所有苹果，也就是直接让苹果的数量翻倍。也就是说，可以均分和这个式子等价（具体的充分必要性我就不证了，绝不是不会）： \ ...

原题链接——Acwing95 解法来源《算法竞赛进阶指南》 想清楚之后并不是很难的题，但个人认为这是对思维提升非常大的一道题，刷新了我对递推和枚举的认识，故记录一下。 首先注意这一题的数据量，n≤500n \leq 500n≤500，数据量较小，同时矩阵也只有5×55 \times 55×5，那么我们可以考虑遍历状态空间，然后取最小值。 问题在于如何遍历，如果直接枚举所有选择，那么就有∑i=16C25i×n\sum_{i=1}^{6}{C_{25}^{i}} \times n∑i=16​C25i​×n种情况，大约是1e8种，大概率会T也许放牛客上能过。 那么接下来让我们回到题目本身，题目的目的是把所有灯都打开。假如我们已经枚举了第一排的可能的操作，但第一排仍有未打开的灯，那么显然只能通过开关相应的第二排的开关来把第一排还未打开的灯打开，同时第二排其他的开关又不能动，因为会破坏第一排本来已经打开的灯的状态，也就是说，第二排的开关操作是固定的，同理，如果第二排操作完后仍有灯关着，那么只能通过操作第三排的相应开关来打开……以此类推，如果在操作完最后一排后最后一排仍有灯关着或者操作步数大于6 ...