数论逆元

Given a positive integer y and a prime p, you are asked to find an integer x such that (x imes y) mod p= 1(x×y) mod p=1. If such x exists, output any x mod p. Otherwise, output -1.

Hint: For any integer a and positive integer b, a mod b is the remainder of a dividing b. Remind that a mod b is non-negative!

The first line of input contains a positive integer T, which is the number of test cases. (1 le T le 200,000)(1≤T≤200,000)
For each test case, there will be one line containing 2 positive integers y, p. ( 1 le y, p le 10^9 )(1≤y,p≤109), p is guaranteed to be a prime)
题意：xy≡1(modp).已知y求解x.
思路：首先看一下一元线性同余方程：ax＝b (modm) , 即ax除以m, 6除以m, 两者余数相同，这里a、b、m都是整数，求解x的值。

方程也可以这样理解：ax-b是m的整数倍。设y是倍数，那么ax-b=my, 移项得到ax-my=b.因为y可以是负数，改写为ax+my=b, 这就是在扩展欧几里得算法中提到的元一次不定方程。

当且仅当gcd (a,m) 能整除b时有整数解。例如15x+6y=9, 有整数解＝1,y=-1.当gcd (a,m) =b时，可以直接用扩展欧几里得算法求解ax+my=b.如果不满足 gcd (a,m) =b, 还能用扩展欧几里得算法求解ax+my=b吗？答案是肯定

的，但是需要结合下面的逆元。

所以这题的b就是1.然后直接套板子就行了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
long long exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    ll ret=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return ret;
}
ll gh(int a,int mod)
{
    ll x,y;
    ll d=exgcd(a,mod,x,y); //利用扩展GCD计算d的值也就是b
    return d==1?(x%mod+mod)%mod:-1;  //如果d是1有解，返回值，否则返回-1
}
int main()
{
    int r;
    scanf("%d",&r);
    while (r--)
    {
        ll a,b;
        scanf("%lld%lld",&a,&b);
        printf("%lld
",gh(a,b));
    }

    return 0;
}