专栏首页mlPOJ--Strange Way to Express Integers

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...

    Gxjun
  • hdu 3074 Zjnu Stadium (带权并查集)

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

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

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

    Gxjun
  • 数据库 连接(JOIN)

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

    lzugis
  • LeetCode 695. 岛屿的最大面积(图的BFS/DFS)

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

    Michael阿明
  • QQ显示IP地址方法

    Youngxj
  • HDUOJ-----2852 KiKi's K-Number(树状数组+二分)

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

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

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

    面向对象思考
  • 联邦政府在云计算支出方面的冲动将扩展到未来

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

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

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

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券