poj2891非互质同余方程

Strange Way to Express Integers

Time Limit: 1000MS		Memory Limit: 131072K
Total Submissions: 8176		Accepted: 2439

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 a₁, a₂, …, a_k. For some non-negative m, divide it by every a_i (1 ≤ i ≤ k) to find the remainder r_i. If a₁, a₂, …, a_k are properly chosen, m can be determined, then the pairs (a_i, r_i) 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 a_i, r_i (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%A=a ①

x%B=b ②

现在给出两种合并的方法:

1）要把①②式合并成 x%C=c ③ 易知C一定是A和B的最小公倍数的倍数，否则不可能同时满足①②两式。

这里我们取C为A,B的最小公倍数，设d=gcd(A,B),则C=A*B/d.

接下来我们只要求出余数c即可，假设p是方程组①②的其中一个解

因为③是①②两式的合并方程，所以p也是③的解，所以可以得到c=p%C

接下来的问题就是怎么求出方程组①②的其中一个解。

首先，满足方程组①的最小解显然就是x=a

然后满足①②的解就是 (a+kA)%B=b,其中x=a+kA（k为任意自然数）

这个方程很明显可以用扩展欧几里德算法即可求得x，这样就完成了两个方程的合并

当所有的同余方程合并成一个方程 x%G=g 时候，g即为最终的最小解。。

 1 #include <iostream>
 2 #include <math.h>
 3 using namespace std;
 4 #define ll long long int
 5 ll funa(ll a,ll b)
 6 {
 7     if(b==0) return a;
 8     return funa(b,a%b);
 9 }
10 void fun(ll a,ll b,ll &x,ll &y)
11 {
12     if(b==0)
13     {
14         x=1;
15         y=0;
16         return ;
17     }
18     fun(b,a%b,x,y);
19     ll  t=x;
20     x=y;
21     y=t-(ll)(a/b)*y;
22 }
23 int main()
24 {
25     ll  n;
26     while(cin>>n)
27     {
28         int i;
29         ll a[n][2];
30         for(i=0;i<n;i++)
31         cin>>a[i][0]>>a[i][1];
32         for(i=1;i<n;i++)
33         {
34             ll z=funa(a[i-1][0],a[i][0]);
35             if((a[i][1]-a[i-1][1])%z!=0)
36             break;
37             ll x,y;
38             fun(a[i-1][0],a[i][0],x,y);
39             x=x*(a[i][1]-a[i-1][1])/z;
40             x=(x%(a[i][0]/z)+a[i][0]/z)%(a[i][0]/z);
41             x=x*a[i-1][0]+a[i-1][1];
42             a[i][0]=a[i-1][0]*a[i][0]/z;
43             a[i][1]=x;
44         }
45         if(i>=n)
46         cout<<a[n-1][1]<<endl;
47         else cout<<-1<<endl;
48     }
49 
50 }
51 
52 //(n+d)%23=p;   (n+d)%28=e;   (n+d)%33=i ,求n 。

View Code