欧拉函数求乘法逆元

欧拉函数的条件是a,p互质，乘法逆元的条件也是a,p互质。
乘法逆元要求：$ax\equiv 1 \pmod p$
欧拉函数：$a^{\phi(p)}\equiv 1 \pmod p$
既然都同余1，合并得：
$ax \equiv a^{\phi(p)} \pmod p$，由于a,p互质，两边同除a得：
$x \equiv a^{\phi(p)-1} \pmod p$
时间复杂度为 $O(log(\phi(p) + \sqrt{p})$
模板：

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL a,p;
LL phi(LL x){
    LL res=x;
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            res=res/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) res=res/x*(x-1);
    return res;
}
LL qmi(LL a,LL k){
    LL res=1;
    while(k){
        if(k&1) res=res*a%p;
        a=a*a%p;
        k>>=1;
    }
    return res;
}
int main(){
    scanf("%lld%lld",&a,&p);
    LL res=qmi(a,phi(p)-1);
    printf("%lld\n",res);
    return 0;
}

和费马小定理相比

时间复杂度比用费马小定理高，小费马是$O(log(p))$.
但是，小费马要求p是质数，而欧拉定理仅仅要求a,p互质。
另外一点就是，用扩欧做得话，时间复杂度也是$O(log(p))$，且也是要求a,p互质就可以。
综合看，扩欧是最优选择。