解題報告 之 POJ2891 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 a₁, a₂, …, a_k. For some non-negative m, divide it by every a_i (1 ≤ i ≤ k) to find the remainderr_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

 

題目大意：現在將數表示成一種新的形式，即用一個數去除多個數mk，分別得到余數rk，用這些（除數，余數）對來唯一確定本來的數字。有了數num和m1~mn很容易表示成這種形式，但是現在反過來，給你n個（mk，rk）對，讓你確定這個數num是多少？不存在輸出-1.

 

分析：裸的解線性同余方程組，說實話我看書沒看懂這個代碼的原理，特別是要用m2/gcd那裡，所以先把代碼當接口來用吧。有一個講解的比較好的博文大家可以看看原理（http://blog.csdn.net/orpinex/article/details/6972654），但是我同樣看不懂，等學了中國剩余再返回來看看吧。那麼這道題等價於解方程：

x ≡ r1（mod m1）

x ≡ r2（mod m2）

……

x ≡ rn（mod mn）

是線性同余方程組，用模版過吧，雖然原理還不懂。。。Orz。。如果有好心的大神願意給我講講麻煩加我QQ吧 452884244，叩謝。

 

上代碼：

 

#include
#include
using namespace std;

typedef long long ll;

ll exgcd( ll a, ll b, ll& x, ll& y )  //擴展gcd
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	ll gcd = exgcd( b, a%b, x, y );
	ll tem = x;
	x = y;
	y = tem - a / b*y;
	return gcd;
}

int main()
{
	int n;
	ll r1, m1, r2, m2, x0, y0;
	while(cin >> n)
	{
		bool flag=1;
		cin >> m1 >> r1;  //以第一個同余方程作為基礎
		for(int i = 1; i < n; i++)
		{
			cin >> m2 >> r2;    //處理剩下的同余方程
			ll a = m1, b = m2, c = r2 - r1;
			ll d=exgcd( a, b, x0, y0 );   //求基礎解X0和d=GCD

			if(c%d != 0) flag = false;  //無解條件

			ll t = b / d;                                        //看不懂，似乎是在更新一些系數。
			x0 = (x0*(c / d) % t + t) % t;			//看不懂，似乎是在更新一些系數。
			r1 = m1*x0 + r1;								//看不懂，似乎是在更新一些系數。
			m1 = m1*(m2 / d);							//看不懂，似乎是在更新一些系數。
		}
		if(!flag)
		{
			cout << -1 << endl;
			continue;
		}
		cout << r1 << endl;
	}
	return 0;
}

數論難起來真是理解無力。。。。