逆元

oasis

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;
}