poj 2417 Discrete Logging 求解模方程a^x=b(mod n),n为素数+模

2019-04-14 19:07发布

站内文章 / 模拟电子
17419 0 1056
#include #include #include #include #include #include using namespace std; #define LL long long //快速幂求a^b LL pow_mod(LL a,LL b,LL n) { LL s=1; while(b) { if(b&1) s=(s*a)%n; a=(a*a)%n; b=b>>1; } return s; } //求解模方程a^x=b(mod n)。n为素数，无解返回-1 //费马小定理a^(n-1)=1(mod n),n为素数。a^0=1,所以循环节小于等于n，即如果存在解，则最小解x<=n LL log_mod (LL a,LL b,LL n) { LL m,v,e=1,i; m=ceil(sqrt(n+0.5)); //x=i*m+j //v=inv(pow_mod(a,m,n),n); //a^m*v=1(mod n) v=pow_mod(a,n-m-1,n); mapx; x[1]=m; for(i=1;i

热门文章