poj 2891 Strange Way To Express Integers(線性同餘方程組)

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, …, akare 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 mod r1=a1

X mod r2=a2

...

...

...

X mod rn=an

首先，我們看兩個式子的情況

X mod a1=r1……………………………………………………………(1)

X mod a2=r2……………………………………………………………(2)

則有 

X=a1*y1+r1………………………………………………………………(*)

X=a2*y2+r2

那麼 a1*y1+r1=a2*y2+r2

整理，得

a1*y1-a2*y2=r2-r1

令(a,b,x,y,m)=(m1,m2,k1,k2,r2-r1)，原式變成

ax+by=m            (a=a1,b=a2,m=r2-r1)

熟悉吧？

對于每一個方程GCD(1,ai) | ri=1|ri=0,方程都有解無需驗證，隻需驗證聯立後的方程是否有解； 

此時，因為GCD(a,b)=1不一定成立，GCD(a,b) | m 也就不一定成立。是以應該先判 若 GCD(a,b) | m 不成立，則！！！方程無解！！！。

否則，繼續往下。

解出(x,y)，将y1=x反代回（*），得到X。

于是X就是這兩個方程的一個特解，通解就是 X'=X+k*LCM(m1,m2)                          //可以分别從方程（1）（2）的通解形式想到

這個式子再一變形，得 X' mod LCM(m1,m2)=X

這個方程一出來，說明我們實作了(1)(2)兩個方程的合并。

令 M=LCM(m1,m2)，R=特解X

就可将合并後的方程記為 X mod M = R。

然後，擴充到n個方程。

用合并後的方程再來和其他的方程按這樣的方式進行合并，最後就能隻剩下一個方程 X mod M=R，其中 M=LCM(m1,m2,...,mn)。

那麼，X便是原模線性方程組的一個特解，通解為 X'=X+k*M。

如果，要得到X的最小正整數解，就還是原來那個方法：

min=(x%t+t)%t;

……………………………………詳見代碼

參考代碼+部分注釋：

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
#include 
       
         #include 
        
          #include
         
           using namespace std; const int maxn=1000000+10; long long a1,a2,r1,r2,x,y; int n; long long extended_gcd(long long a,long long b,long long &x,long long &y)//擴充歐幾裡得算法：求等式ax+by=gcd(a,b)中的x,y；傳回d=gcd(a,b) { if(b==0) {x=1;y=0;return a;} long long d=extended_gcd(b,a%b,y,x); y-=a/b*x; return d; } long long solve() { cin>>a1>>r1; bool ok=true; while(--n){ cin>>a2>>r2; long long a=a1,b=a2,m=r2-r1; long long d=extended_gcd(a,b,x,y); //求出線性系數 x 和 gcd(a,b) if(m%d) ok=false; //存在一組方程無解就标記，注意不能return ,否則資料沒有讀完就輸出了，WA x=((x*m/d)%(b/d)+(b/d))%(b/d); //求ax+by=m的最小正整數解，注意從擴充歐幾裡得算法處了解 r1=x*a1+r1; //r1即為方程的一個特解 a1=(a1*a2)/d; //a1=lcm(a1,a2) } if(ok) return r1; else return -1; } int main() { // freopen("input.txt","r",stdin); while(cin>>n){ cout<
          
           <