欧拉定理+费马小定理+快速幂求逆元+欧几里得算法求逆元+线性同余方程

乘法逆元：

      假设  a / b ≡ c (mod p)，b * x ≡ 1 (mod p)  

    那么  a * x ≡ c (mod p) 如下图，利用到了模运算对乘法的分配率，因为其中一个的余数恒为1，所以有，(（99/3）*（3*7）)%10==(((99/3)%10) * ((3*7)%10))%10==(3 * 1)%10==3.

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          

欧拉定理：若 a,p互质，则有a^φ(p)=1(mod p)

费马小定理：若p为质数，a^p≡a(mod p)等同于 a^p-1≡1(mod p) φ(p)=p-1

当p为质数时，可以用快速幂求逆元：

a / b ≡ a * x (mod p)

两边同乘 b 可得 a ≡ a ^ b ^ x (mod p)

即 1 ≡ b * x (mod p)

同 b * x ≡ 1 (mod p)

由费马小定理可知，当 p 为质数时

b^(p - 1) ≡ 1 (mod p)

拆一个 b 出来可得 b * b^(p - 2) ≡ 1 (mod p)

故当 p 为质数时，b 的乘法逆元 x = b^(p - 2)

#include
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
ll qmi(ll a,ll k,ll p)
{
    ll res=1;
    while(k)
    {
        if(k&1) res=res*a%p;
        k>>=1;
        a=a*a%p;
    }
    return res;
}
int main()
{
    ll a,p;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&a,&p);
        if(a%p==0)
            printf("impossible\n");
        else
            printf("%lld\n",qmi(a,p-2,p));
    }
     return 0;
}

欧几里得算法求逆元：

当ax+by==gcd(a,b)这条式子中a，b互质时,原式相当于ax+by==1，此时有ax≡1(mod b)

相当于ax≡1(mod p)

此时有x是a的逆元

该式子比快速幂求逆元应用范围广，即使p不是质数也成立，但仍然需要a,b互质。

#include
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
void exgcd(ll a,ll b,ll &x,ll &y )
{
    if(b==0){ x=1,y=0;return;}
   exgcd(b,a%b,x,y);
    ll t=x;
    x=y;
    y=t-y*(a/b);
}
int main()
{
    ll a,b,x,y;
    int t;
    cin>>t;
    while(t--)
    {
    scanf("%lld%lld",&a,&b);
    exgcd(a,b,x,y);
    cout<
    }
     return 0;
}