# POJ 2891 Strange Way to Express Integers （扩展欧几里得）

## Description

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:

Choose k different positive integers a1, a2, …, ak. For some non-negative m, divide it by every ai (1 ≤ i ≤ k) to find the remainder ri. If a1, a2, …, ak are properly chosen, m can be determined, then the pairs (ai, ri) can be used to express m.

“It is easy to calculate the pairs from m, ” said Elina. “But how can I find m from the pairs?”

Since Elina is new to programming, this problem is too difficult for her. Can you help her?

## Input

The input contains multiple test cases. Each test cases consists of some lines.

Line 1: Contains the integer k.

Lines 2 ~ k + 1: Each contains a pair of integers ai, ri (1 ≤ i ≤ k).

## Output

Output the non-negative integer m on a separate line for each test case. If there are multiple possible values, output the smallest one. If there are no possible values, output -1.

## Sample Input

2
8 7
11 9


## Sample Output

31


## 思路

$X\%m_0=r_0$ 与 $X\%m_1=r_1$ ，等价于 $X=m_0×k_0+r_o=m_1×k_1+r_1$ ，其中 $k_i$ 为一整数。

$a×x_0+b×y_0=\gcd(a,b)$ 等同于 $a×x_0+\frac{a×b}{\gcd(a,b)}k+b×y_0-\frac{a×b}{\gcd(a,b)}k=\gcd(a,b)$

## AC 代码

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<iostream>
using namespace std;
#include<queue>
#include<map>
#define INF (1<<25)

typedef __int64 LL;
#define maxn 10005
LL m[maxn],r[maxn];
int n;

LL ex_gcd(LL a, LL b, LL &x, LL &y)
{
LL d = a;
if(b != 0)
{
d  = ex_gcd(b, a % b, y, x);
y -= (a/b) * x;
}
else x = 1, y = 0;
return d;
}

LL solve()
{
LL M=m[0],R=r[0],gcd,x,y;
for(int i=1; i<n; i++)
{
gcd=ex_gcd(M,m[i],x,y); // 扩展欧几里得求系数 x y gcd
if((r[i]-R)%gcd)return -1;  // 如果无法整除即无解
LL k=(r[i]-R)/gcd*x%(m[i]/gcd); // 求k0
LL X=k*M+R;     // 代回原式求X
M=M/gcd*m[i];   // M变为lcm
R=(X+M)%M;      // R变为此时最小的X
}
return R;
}

int main()
{
while (~scanf("%d",&n))
{
for (int i = 0; i < n; ++i)
scanf("%I64d%I64d", &m[i], &r[i]);
printf("%I64d\n",solve());
}
return 0;
}