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 1695 GCD (欧拉函数,容斥原理)

GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

2702
来自专栏HansBug's Lab

3212: Pku3468 A Simple Problem with Integers

3212: Pku3468 A Simple Problem with Integers Time Limit: 1 Sec  Memory Limit: 12...

3318
来自专栏算法修养

浙江工业大学校赛 小马哥和数列

小马哥和数列 Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

2976
来自专栏ml

HDU-----(1083)Courses(最大匹配)

Courses Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K ...

2737
来自专栏HansBug's Lab

1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐

1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐 Time Limit: 5 Sec  Memory Limit: 64 MB Subm...

3477
来自专栏小樱的经验随笔

HDU 2561 第二小整数

第二小整数 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

3448
来自专栏算法修养

POJ-1458 Common Subsequence(线性动规,最长公共子序列问题)

Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submis...

3287
来自专栏算法修养

HDU-1003 Max Sum(动态规划,最长字段和问题)

Max Sum Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J...

5875
来自专栏ml

hdu---(3779)Railroad(记忆化搜索/dfs)

Railroad Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (...

3525
来自专栏ml

HDUOJ---A + B Again

A + B Again Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 ...

29311

扫码关注云+社区

领取腾讯云代金券