题目链接： http://poj.org/problem?id=2417 题目大意： 已知整数P、B、N满足公式B^i = N(mod P)，求i的值是多少。 思路： 典型的解高次同余方程A^x = B(mod C)，直接套模板解决。注意输入顺序：C A B AC代码： #include<iostream>#include<algorithm>#inclu

当n是素数时 a^x≡b (mod n) 令x=im+j，m=ceil(sqrt(n))   0<=i,j<m a^j≡b*(a^(-m))^i    mod(n) 用hash表存储a^0,a^1……a^(m-1)，枚举i，找是否存在对应的j，存在即有解 n 不是素数之所以不成立是因为 ( a,n )!=1 导致逆元不存在。 a^x-kn=b; 当n不是素数时