爱用建站官网,公司网站文化活动备案,以用户为中心 建设学校网站,如何建设网页制作的网站在a|b(a能整除b)的前提下#xff0c;计算(b/a)mod m的时候转化为 计算(b*x)mod m ; 这时的x就是a的逆元(a模m的逆元)#xff1b;此时x满足 (a*x mod m 1)#xff1b; 这个x的求法有一下两种#xff1a;1)扩展欧几里得算法求解 a*xm*y1; 因为 a*x mod m 1 a…在a|b(a能整除b)的前提下计算(b/a)mod m的时候转化为 计算(b*x)mod m ; 这时的x就是a的逆元(a模m的逆元)此时x满足 (a*x mod m 1) 这个x的求法有一下两种1)扩展欧几里得算法求解 a*xm*y1; 因为 a*x mod m 1 a*x1m1*y a*xm*y1 ( m-m1 )。LL ExGcd(LL a,LL b,LL x,LL y){if(!b){x1;y0;return a;}LL ansExGcd(b,a%b,x,y);LL tempx;xy;ytemp-a/b*y;return ans;}LL getInverse(LL a,LL p)//a模n的乘法逆元{if(__gcd(a,p)!1)return -1;LL x,y;ExGcd(a,p,x,y);return (xp)%p;}2)如果有gcd(a,m)1 即a,m互质则a^(m-1) mod m1 (这个定理在此不证明有兴趣去搜) ; 所以 [ a^(m-2) ] mod m 等价于 a^(-1) 此时a的逆元就是a^(-1)x [ a^(m-2) ] mod m 。LL qpowMod(LL m,LL n,LL p){LL ans1;LL tempm;while(n0){if(n1)ansans*temp % p;temptemp*temp % p;n1;}return ans;}LL _getInverse(LL a,LL p){return qpowMod(a,p-2,p);}此外 当a,m不是互质数计算(b/a)mod m没办法把b/a转换成b×(a的逆元)可以用 (b/a)mod m [ b mod (a*m) ] / a 来代替。
