整理完之后发现，这类题本身难度不算特别大，但我之前因为数学基础薄弱，很多关键点理解不到位；再加上没有熟悉的解题模板/套路，导致遇到不互素的题目时经常卡住，甚至做不出来。现在把这类问题系统地整理一下，方便之后复盘和套用。 整体思路：e小的时候使用有限域开方，e如果比较大，需要使用AMM算法，常用算法还有CRT算法和hensel定理。 AMM算法是什么：本质上也是一种有限域开方。 CRT什么时候用：如果说m的位数比较小，小于其中一个素数，那么就不需要使用CRT，如果CRT的位数比较大，则需要在各素数下进行有限域开方，然…