话说前几天（似乎是很久很久以前
）写了数论相关。
怎么说也应该写几道题，然而因为我太傻了写的都是傻逼题。
http://www.lydsy.com/JudgeOnline/problem.php?id=1407 代码
看起来很厉害，然而题面里保证了答案不超过$10^6$。所以只要枚举所有可能的答案，列出同余方程，用扩展欧几里得算法求解以判定解是否合法。
注意答案要从$\max C_i$开始枚举，否则输入的洞穴编号$C_i$将没有意义。因为这个WA了好久。。。
http://www.lydsy.com/JudgeOnline/problem.php?id=2242 代码
3个操作分别使用快速幂，扩展欧几里得，BSGS计算。
http://www.lydsy.com/JudgeOnline/problem.php?id=3122 代码
特判掉$X_1=t$和$a=0$的情况。
若$a=1$，通项式为$X_n\equiv X_1+\left(x-1\right)b\pmod p$，使用扩展欧几里得算法。
对于其他情况，通项式为$X_n\equiv a^{x-1}x+b\frac{x^{n-1}-1}{a-1}\pmod p$。
使用扩展欧几里得算法求出$a^{x-1}$，再用BSGS计算出$x$即可。
http://www.lydsy.com/JudgeOnline/problem.php?id=4128 代码
有一个做法：将BSGS算法推广到矩阵上，用矩阵求逆的算法来求逆元。
看起来很对的样子，网上甚至还有一篇题解中对BSGS算法做了一点变形，避免了求逆的过程。（似乎是错误的，但可以AC）
然而这个做法实际上是错误的。BSGS算法是基于欧拉定理得出的，显然矩阵乘法并不满足这个性质，所以这样的做法只能正确处理答案在$\left[0,p-1\right)$的输入数据。
不过因为数据比较弱，用这个做法在BZOJ是可以AC的。
本人暂时没有找到复杂度较低的正确做法。
http://www.lydsy.com/JudgeOnline/problem.php?id=1951 代码
一道综合性的数论题。
题面很长，但就是要计算$G^{\sum_\limits{k\mid N}{N\choose k}}\bmod 999911659$。
外面只要一个快速幂即可，考虑组合数部分。
暴力求组合数显然是不行的，考虑卢卡斯定理（即对于质数$P$，有${n\choose m}\equiv{n\bmod P\choose m\bmod p}\times{\left\lfloor n/P\right\rfloor\choose\left\lfloor m/P\right\rfloor}\pmod P$），这样可以预处理阶乘及其逆元，用通项式计算前一部分，递归计算后一部分。
然而题目中的模数不是质数，而且它太大了，就算能使用卢卡斯定理也不够快。
将模数分解质因数，得到$999911659=2\times 3\times 4679\times 35617$。
发现如果分别计算对于模这些质因数的结果，因为模数没有相同的质因数，所以可以用中国剩余定理合并出要求的解。
最后的时间复杂度为$\mathcal{O}\left(\sum_\limits{k\mid 999911659}k+\sqrt N\log_k N\right)$
评论 (0)
