数学--数论--POJ281（线性同余方程）

埃琳娜（Elina）正在阅读刘如家（Rujia Liu）写的书，其中介绍了一种表达非负整数的奇怪方法。方式描述如下：

选择k个不同的正整数a 1，a 2，…，a k。对于一些非负米，把它由每一个我（1≤ 我 ≤ ķ）找到其余ř 我。如果一个1，一个2，…，一个ķ适当地选择，M可以是确定的，则对（一个我，- [R 我）可被用来表达米。

“从m来计算对很容易，” Elina说。“但是我怎么能从两对中找到m？”

由于Elina是编程新手，所以这个问题对她来说太难了。你能帮她吗？

输入项

输入包含多个测试用例。每个测试用例由几行组成。

第1行：包含整数k。

线2〜ķ + 1：每个包含一对整数一个我，- [R 我（1≤ 我 ≤ ķ）。

输出量

对于每个测试用例，在单独的行上输出非负整数m。如果有多个可能的值，请输出最小的一个。如果没有可能的值，则输出-1。

样本输入

2

8 7

11 9

样本输出

31

题目大意：现在将数表示成一种新的形式，即用一个数去除多个数mk，分别得到余数rk，用这些（除数，余数）对来唯一确定本来的数字。有了数num和m1~mn很容易表示成这种形式，但是现在反过来，给你n个（mk，rk）对，让你确定这个数num是多少？不存在输出-1.

裸的解线性同余方程组。

直接上扩展偶近距离的定理完事。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <cmath>

using namespace std;

typedef long long ll;

const ll p = 9973;

void exgcd(ll a, ll b, ll &d, ll &x, ll &y)

{

    if (!b)

    {

        x = 1, y = 0, d = a;

        return;

    }

    exgcd(b, a % b, d, y, x);

    y -= (a / b) * x;

}

int main()

{

    while (~scanf("%I64d", &n))

    {

        ll a1, r1, a2, r2;

        scanf("%I64d%I64d", &a1, &r1);

        bool flag = 1;

        REP(i, 2, n)

        {

            ll d, x, y;

            scanf("%I64d%I64d", &a2, &r2);

            ll ans = 0;

            exgcd(a1, a2, d, x, y); //扩展欧几里德算法

            if ((r2 - r1) % d)

                flag = 0; //扩展欧几里德算法的性质，如果不能整除，则无法合并。

            else

            {

                x *= ((r2 - r1) / d);

                ll n1 = a2 / d;

                x = (x % n1 + n1) % n1; //x不断地加a2/gcd直到x大于0，如果用循环的话会超时，x可以通过直接取模计算。由于这里用不到y的值，所以暂时可以不用管

                r1 = a1 * x + r1;       //这相当于是x0的值

                a1 = (a1 * a2) / d;     //将a1变成a1和a2的最小公倍数

            }

        }

        if (flag)

            printf("%I64d\n", r1);

        else

            printf("-1\n");

    }

}

巴特西

数学--数论--POJ281（线性同余方程）

最新文章

热门文章