首先我们来认识一下离散对数。
离散对数是一种在整数中基于同余运算和原根的对数运算。当模有原根时,设为模的一个原根,则当
时,。此处的是以整数为底模的离散对数值。
之前做过一个题,题意是这样的:求同余方程的解,其中是素数。
分析:对于本题,我们利用离散对数的知识,先求模的一个原根,那么就有,对于,用Baby
Step Giant Step能很好地解决,那么这样我们再用扩展欧几里得算法可以计算出,快速幂再进一步求,所以这样本题完美解决。
那么,如果为合数呢?
其实,如果为合数,我们要做的第一件事就是把素因子分解,即,那么我们分别计算,然后用CRT合并即可。
那么对于,有两种情况:
(1)
(2)
对于情况(1),我们就直接先求原根,然后利用离散对数来解决。
而对于情况(2),我们有,这样就转化为情况(1)了。
假设对于每个的解的个数为,那么方程的解的个数为。
题目:http://acm.hdu.edu.cn/showproblem.php?pid=3731
题目:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1123