exgcd O(log n) , 实质是斐波那契数列

a*b==1(mod p)  -> a*b + k*p ==1 (mod p)

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b) {
        x = 1 , y = 0 ; return a ;
    }
    ll ex = exgcd(b,a%b,y,x);
    y-=a/b*x;
    return ex ;
}
int main() /// 求a在mod下的逆元
{
    ll x , y ;
    ll gcd = exgcd(a,mod,x,y);
    ll ex = ( gcd==1?(x%mod+mod)%mod : -1 ) ;
}

费马小定理 O(log mod)

P为素数，那么a^（p-1）= 1（%p）
a^(p-2)*a = 1(%p) -> a^(p-2) = 1/a ，即a^(p-2)是a的逆元

ll ksm(ll a,ll p,ll mod)
{
    ll ans = 1 ;
    while(p){
        if(p&1) ans = ans*a % mod ;
        p>>=1;
        a = a*a%mod;
    }
    return ans ;
}
int main()
{
    ll inv = ksm(a,mod-2,mod); /// 求a的逆元
}

线性求逆元

ll inv[mxn] ;
void Inv(ll mod)
{
    inv[1] = 1 ;
    for(int i=2;i<mod;i++) inv[i] = (mod-mod/i)*inv[mod%i]%mod;
}

欧拉定理

ll euler(ll n)
{
    ll res = n ;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            res = res/i*(i-1) ;
            while(n%i==0) n/=i;
        }
    }
    if(n>1) res = res/n*(n-1);
    return res ;
}

void Phi()
{
    for(int i=1;i<mxn;i++) phi[i] = i;
    for(int i=2;i<mxn;i++){
        if(phi[i)==i){
            for(int j=1;j<mxn;j+=i)
                phi[j] = phi[j]/i*(i-1);
        }
    }
}

int main()
{
    ll inv = ksm(x,Phi(mod)-1); /// 求X的逆元
}