扩展欧几里德 get ！

· · 个人记录

从现在开始，

好好学数论

妈耶：

传送门

刚学扩欧的时候

真的是想大喊 “妈耶！这啥！”

不过，最后好歹是学会了

让我们来看看是怎么推出来的：

a \times x_1 +b\times y_1 = \gcd(a,b) \gcd(a,b) = \gcd(b\ ,\ a\%b) \gcd(b\ ,\ a\%b) = b\times x_2 +(a\%b)\times y_2 a\%b = a-\lfloor a/b \rfloor \times b a \times x_1 + b \times y_1 = b \times x_2 + (a-\lfloor a/b\rfloor \times b) \times y_2 a \times x_1 + b \times y_1 = b \times x_2 + a \times y_2 - \lfloor a/b \rfloor \times b \times y_2 a \times x_1 + b \times y_1 = a \times y_2 + b \times [x_2 - \lfloor a/b \rfloor \times y_2]

∴ x_1 = y_2 \ ,\ y_1 = x_2 - \lfloor a/b \rfloor \times y_2

∴ y_1 = x_2 - \lfloor a/b\rfloor \times x_1

这个不是很显然，

但认真看的话还是能看懂的

好了

上模板：

int Exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    int g = Exgcd(b,a%b,y,x);
    y -= (a/b)*x;
    return g;
}

int main(void)
{
    cin >> a >> b;
    Exgcd(a,b,x,y);
    cout << (x+b)%b;    //这里，为了防止出现负数进行的修正
    return 0;
}

由于扩欧只是求出了一组解，

想要找到其他解的话需要不断地 x += lcm ( a , b ) / a , y += lcm ( a , b ) / b

困惑：

传送门

一道让人困惑的题。。。尤其是那个模数

如题， a / b % p 肯定是没法直接做的。

这个时候就需要逆元来求了。

先来讲讲逆元吧

b 的逆元就是 b*x ≡ 1 ( mod p ) 的解

记 b 的逆元为 b ^ ( -1 )

那么，怎么求逆元呢？

再来先来看看逆元的公式 b*x ≡ 1 ( mod p )

 b*x ≡ 1 ( mod p )

 即：(b*x) % p = 1

 ∵ a % b = (a/b)*b

   也就是 a 减去整数倍的 b

 ∴ (b*x) % p = xb - ap

 ∴ xb - ap = 1

 化成这样之后，就可以用扩展欧几里得求解了

这样就求出了 b 的逆元。

然后，a / b % p 也就是 a * x % p

贴代码

const int p = 19260817;
long long a,b,x,y;

long long read()
{
    long long x = 0;
    char c = getchar();
    while(c>'9' || c<'0')   c = getchar();
    while(c<='9' && c>='0')
    {
        x = (x*10+(c-'0')) % p;
        c = getchar();
    }
    x = x % p;
    return x;
}

long long Exgcd(long long a, long long b, long long & x, long long & y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    long long g = Exgcd(b,a % b,y,x);
    y -= a/b*x;
    return g;
}

int main(void)
{
    a = read();
    b = read();
    long long g = Exgcd(b,p,x,y);
    if(g != 1)
    {
        cout << "Angry!";
        return 0;
    }
    x = (x+p)%p;
    cout << a*x % p;
    return 0;
}