链接:

https://www.acwing.com/problem/content/205/

题意:

求关于x的同余方程 ax ≡ 1(mod b) 的最小正整数解。

思路:

首先:扩展欧几里得推导.

有ax+by = gcd(a, b) = gcd(b, a%b),

ax+by = bx+(a%b)y

ax+by = bx+(a-(a/b)b)y

ax+by = bx + ay-(a/b)by

ax+by = ay + b(x-a/by)

有x' = y, y' = x-a/by

递归求解

对于ax = 1 (mod b).有b | ax+1. 令 ax+1 = -yb.

有ax+by = 1.用扩展欧几里得可以求出一个解.

代码:

#include <bits/stdc++.h>

using namespace std;

int ExGcd(int a, int b, int &x, int &y)

{

    if (b == 0)

    {

        x = 1, y = 0;

        return a;

    }

    int d = ExGcd(b, a%b, x, y);

    int tmp = y;

    y = x-(a/b)*y;

    x = tmp;

    return d;

}

int main()

{

    int a, b, x, y;

    scanf("%d%d", &a, &b);

    int gcd = ExGcd(a, b, x, y);

    printf("%d\n", ((x%b)+b)%b);

    return 0;

}

巴特西

Acwing-203-同余方程(扩展欧几里得)

链接:

题意:

思路:

代码:

最新文章

热门文章