N 次剩余

例题

题目链接 51nod 1038 求解方程 X^A\ \equiv\ B\ (Mod\ P) 所有小于 p 的正整数解。
 

预备知识

离散对数(BSGS 算法)
原根
线性同余方程(扩展欧几里得)
 

做法

先求出 p 的最小原根 g. 接着可以用 BSGS 算法求出 B = g ^ t. 不妨另 X = g ^ y. 那么原方程则为 (g^y)^A\ \equiv\ g^t\ (Mod\ P). 由费马小定理得 Ay\ \equiv\ t\ (Mod\ p-1). 这样就将问题转化成了一个线性同余方程,用扩展欧几里得可以解出所有解。之后去重便可得到答案。
因为本题数据较大,所以在 BSGS 算法时,使用 Map 效率会变低,所以得手写 hash. 或者手写一个二分查找,在这里我写的是二分查找。
 

代码

 

另一个例子

题目链接 51nod 1039 这道题是求解三次剩余,标算并不是这样,但是可以用 N 次剩余加特判卡过去,因为手写二分会超时,所以在这里是使用了 hash 来让 BSGS 不超时。
 

代码

 

完结

发表评论

电子邮件地址不会被公开。 必填项已用*标注