# POJ--Strange Way to Express Integers

Strange Way to Express Integers

Time Limit: 1000MS

Memory Limit: 131072K

Total Submissions: 8370

Accepted: 2508

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 ≤ ik) 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 ≤ ik).

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`

Hint

All integers in the input and the output are non-negative and can be represented by 64-bit integral types.

Source

POJ Monthly--2006.07.30, Static

``` 1 void exgcd(int a,int b,int * x,int  *y,int  * d)
2 {
3    if(b==0)
4 {
5  x=1,y=0,d=a;
6 }
7 else
8 {
9    exgcd(b,a%b,x,y,d);
10 int temp=x;
11 x=y,y=temp-a/b*y;
12 }
13 }```

``` 1 int sove()
2 {
3     scanf("%d%d",&a1,&r1);
4     for(i=0;i<n;i++)
5     {
6         scanf("%d%d",&a2,r2);
7         a=a1,b=a2,c=r2-r1;
8         exgcd(a,b,x,y,d);
9         if(c%d!=0)
10         {
11             ifhave=0;
12         }
13         int t=b/d;
14         x=(x*(c/d)%t+t)%t;
15         r1=r1+x*a1;
16         a1=a1*(a2/d);
17     }
18     if(!ifhave)
19     {
20         r1=-1;
21     }
22    return r1;  //即为解的个数
23 }```

``` 1 #include<stdio.h>
2 #define LL long long
3 LL x,y,q;
4 void exgcd(LL a,LL b)
5 {
6     if(b==0)
7     {
8         x=1,y=0,q=a;
9     }
10     else
11     {
12         exgcd(b,a%b);
13         LL temp=x;
14         x=y,y=temp-a/b*y;
15     }
16 }
17
18 int main()
19 {
20     LL a1,r1,a2,r2,n,i;
21     bool ifhave;
22   while(scanf("%I64d",&n)!=EOF)
23   {
24
25       scanf("%I64d%I64d",&a1,&r1);
26       ifhave=true;
27      for(i=1;i<n;i++)
28      {
29          scanf("%I64d%I64d",&a2,&r2);
30          exgcd(a1,a2);
31          if((r2-r1)%q)
32          {
33              ifhave=false;
34          }
35          LL t=a2/q;
36          x=(x*((r2-r1)/q)%t+t)%t;
37          r1+=a1*x;
38          a1*=(a2/q);
39      }
40      if(!ifhave) r1=-1;
41      printf("%I64d\n",r1);
42   }
43 return 0;
44 }```

0 条评论

• ### hdu-----(1532)Drainage Ditches(最大流问题)

Drainage Ditches Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3...

• ### hdu 3074 Zjnu Stadium （带权并查集）

Zjnu Stadium Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

• ### hdu----149850 years, 50 colors(最小覆盖点)

50 years, 50 colors Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 3276...

• ### 数据库 连接（JOIN）

连接运算中有两种最为重要的连接，一种是等值连接（Equijoin），另一种是自然连接（Nature Join）：等值连接是从关系R和S中的笛卡尔积中选取A，B属...

• ### LeetCode 695. 岛屿的最大面积（图的BFS/DFS）

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个...

• ### HDUOJ-----2852 KiKi's K-Number（树状数组+二分）

KiKi's K-Number Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32...

• ### C++核心准则ES.47: 使用nullptr表现空指针，而不是0或NULL​

Readability. Minimize surprises: nullptr cannot be confused with an int. nullptr...

• ### 联邦政府在云计算支出方面的冲动将扩展到未来

在COVID-19大流行期间，云技术的使用迅速扩展以支持远程工作，这突显了美国政府在未来几年内可能会持续保持越来越高的云采用率。 Deltek高级首席研究分析师...

• ### 51Nod 1289 大鱼吃小鱼(模拟，经典好题)

1289 大鱼吃小鱼            题目来源：             Codility 基准时间限制：1 秒 空间限制：131072 KB 分值: ...