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

#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");
    }
}