链接:

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

题意:

给定2n个整数a1,a2,…,an和m1,m2,…,mn,求一个最小的非负整数x，满足∀i∈[1,n],x≡mi(mod ai)。

思路:

扩展中国剩余定理模板题.

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL R[50], M[50];

int n;

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

{

    if (b == 0)

    {

        x = 1, y = 0;

        return a;

    }

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

    LL tmp = y;

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

    x = tmp;

    return d;

}

LL ExCRT()

{

    LL m = M[1], r = R[1], x, y, gcd;

    for (int i = 2;i <= n;i++)

    {

        gcd = ExGcd(m, M[i], x, y);

        if ((r-R[i])%gcd != 0)

            return -1;

        x = (r-R[i])/gcd*x%M[i];

        r -= m*x;

        m = m/gcd*M[i];

        r %= m;

    }

    return (r%m+m)%m;

}

int main()

{

    scanf("%d", &n);

    for (int i = 1;i <= n;i++)

        scanf("%lld%lld", &M[i], &R[i]);

    printf("%lld\n", ExCRT());

    return 0;

}

巴特西

Acwing-204-表达整数的奇怪方式(扩展中国剩余定理)

链接:

题意:

思路:

代码:

最新文章

热门文章