记录编号	230376	评测结果	AAAAAAAAAAAAAAA
题目名称	[POI 2005] 骑士	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2016-02-21 16:07:05	内存使用	0.29 MiB

#include <fstream>
#include <algorithm>
#define N 110
using namespace std;
typedef long long ll;
ifstream in("knight_poi2005.in");
ofstream out("knight_poi2005.out");
int n;
int A[N]={0},B[N]={0};
int ansa[5]={0},ansb[5]={0};
int temp[5]={0};
void read()
{
	int i;
	in>>n;
	for(i=1;i<=n;i++)
	{
		in>>A[i]>>B[i];
		if(A[i]<0)A[i]*=-1,B[i]*=-1;
	}
}
ll gcd(ll a,ll b)
{
	while(true)
	{
		if(!a)return b;
		if(!b)return a;
		if(a>b)a%=b;
		else b%=a;
	}
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)
	{
		x=1;y=0;
	}
	else
	{
		exgcd(b,a%b,x,y);
		ll t;
		t=x;
		x=y;
		y=t-(a/b)*x;
	}
}
void work()
{
	int i;
	ll d,x,y,a1,a2,a3,b1,b2,b3;
	d=gcd(A[1],A[2]);
	ansa[1]=d;
	exgcd(A[1],A[2],x,y);
	ansb[1]=B[1]*x+B[2]*y;
	ansa[2]=0;
	ansb[2]=labs((A[1]*B[2]-A[2]*B[1])/d);
	for(i=3;i<=n;i++)
	{
		//out<<i<<endl;
		a1=ansa[1];
		b1=ansb[1];
		a2=ansa[2];
		b2=ansb[2];
		a3=A[i];
		b3=B[i];
		d=gcd(a1,a3);
	    exgcd(a1,a3,x,y);
		
		ansa[1]=d;
		ansb[1]=b1*x+b3*y;
		
	    temp[1]=0;
	    temp[2]=labs((a1*b3-a3*b1)/d);
		
		if(!ansb[2])
		{
			ansa[2]=temp[1];
			ansb[2]=temp[2];
		}
		else ansb[2]=gcd(ansb[2],temp[2]);
	}
	out<<ansa[1]<<' '<<ansb[1]<<endl;
	out<<ansa[2]<<' '<<ansb[2]<<endl;
}
int main()
{
	read();
	work();
	return 0;
}