乘法逆元求解

递推打表求逆元

void init()
{fac[0] &＃61; invfac[0] &＃61; pow2[0] &＃61; fac[1] &＃61; invfac[1] &＃61; 1;///初始化pow2[1] &＃61; 2;for (int i &＃61; 2; i < N; i&＃43;&＃43;){fac[i] &＃61; fac[i - 1] * i % mod;///阶乘invfac[i] &＃61; (mod - mod / i) * invfac[mod % i] % mod;///递推打表求逆元O(n),费马小定理是O(n)*log(n)pow2[i] &＃61; pow2[i - 1] * 2 % mod;///2的次幂}for (int i &＃61; 2; i < N; i&＃43;&＃43;)invfac[i] &＃61; invfac[i] * invfac[i - 1] % mod;///逆元阶乘
}


费马小定理求逆元

x的逆元是qsm(x,mod-2);

欧拉函数求逆元

扩展欧几里得算法求逆元

int exgcd(int a, int b, int &x, int &y)
{ ///x,y起初不知道,是递归往上求解x,yif (b &＃61;&＃61; 0){x &＃61; 1, y &＃61; 0;return a;///两处return }int d &＃61; exgcd(b, a % b, x, y);int tmp &＃61; x;x &＃61; y, y &＃61; tmp - (a / b) * y;return d;///记得要返回d啊///【a*x&＃43;b*y&＃61;1中,x是a在模b下的逆元,y是b在模a下的逆元】///【若a*x&＃43;b*y&＃61;c有解,则有gcd(a,b)|c】
}


循环找解求逆元