今天学了一下逆元这个东西，发现这个东西真是神奇。
对于正整数a和m，如果有ax≡ 1(mod m)，那么把这个同余方程中的x最小正整数解叫做a模m的逆元，记作a^-1。大部分情况下都是a和m是互质的。逆元这个东西对于解决a/b模一个数很有用。因为只有加减乘可以和取模换序，所以碰到除法时，运用逆元就又转化成了乘法。下面介绍几个常用的求逆元的方法。（都在a与m互质的前提下）
1.扩展欧几里得。aa^-1≡ 1(mod m)，可以转换为aa^-1 + my = 1，即是扩展欧几里得所能解的ax + by = gcd(a, b) void gcd(int a,int b,int &d,int& x,int& y) { if(!b){ d=a; x=1; y=0; } else { gcd(b,a%b,d,y,x); y-=x*a/b; } } //求解ax+my=gcd(a,m)，亦即ax≡1(mod m)，这时候的x即为逆元 2、费马小定理
由费马小定理a^(m-1)≡ 1(mod m)，即a*a^(m-2))≡ 1(mod m)，那么a^(m-2)即为其逆元，通常m会很大，这时候用快速幂来求。 ll kuai(ll x,ll m)//m=mod-2 { ll ans=1; x%=mod; while(m) { if(m%2) ans=(ans*x)%mod; x=(x*x)%mod; m/=2; } return ans; }