逆元
-
1.单位元:当他与其他元素结合时,并不会改变那些元素。若ae=a,e称为右单位元;若ea=a,e称为左单位元,若ae=ea=a,则e称为单位元
2.逆元:一个存在单位元素e的代数系统 ,如果对S内的元素a存在 ,使得 ,则称 为a对运算“ ”的左逆元素,亦称左逆元。 若有 ,则称 为a对运算“ ”的右逆元素,亦称右逆元。
3.求解公式:(a/b)%m:
设c是b的逆元,则有b*c≡1(mod m);
则(a/b)%m = (a/b)1%m = (a/b)bc%m = ac(mod m);
逆元求法1:
aX≡1 mod n
这个方程等价于求一个X和K,满足
aX=nK+1 (其中X和K都是整数)
则可扩展欧几里得求逆元ax≡1(mod n)
ll extend_gcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1, y = 0; return a; } else { ll r = extend_gcd(b, a % b, y, x); y -= x * (a / b); return r; } } ll inv(ll a, ll n) { ll x, y; extend_gcd(a, n, x, y); x = (x % n + n) % n; return x; }
逆元求法2:
费马小定理:假如p是质数,且gcd(a,p)=1,那么 a(p-1)≡1(mod p),即:假如a是整数,p是质数,且a,p互质,那么a的(p-1)次方除以p的余数等于1。
由上方的公式很容易推导出:a*a(p-2)≡1(mod p)对于整数a,p,a关于p的逆元就是a^(p-2)
int quick_pow(int a,int b){ int r=1,base=a; while(b){ if(b&1) r*=base; base*=base; b>>=1; } return r; }
ps: 快速幂(取模MOD):
ll pow(ll a,ll i){ if (i==0) return 1; int temp=pow(a,i>>1); temp=temp*temp%MOD; if (i&1) temp=(ll)temp*a%MOD; return temp%MOD; }