poj 2891 Strange Way to Express Integers【扩展中国剩余定理】

扩展中国剩余定理板子

#include<iostream>

#include<cstdio>

using namespace std;

const int N=100005;

int n;

long long m[N],r[N],M,R,x,y,d;

void exgcd(long long a,long long b,long long &d,long long &x,long long &y)

{

	if(!b)

	{

		d=a,x=1,y=0;

		return;

	}

	exgcd(b,a%b,d,y,x);

	y-=a/b*x;

}

int main()

{

	while(~scanf("%d",&n))

	{

		bool fl=0;

		for(int i=1;i<=n;i++)

			scanf("%lld%lld",&m[i],&r[i]);

		R=r[1],M=m[1];

		for(int i=2;i<=n;i++)

		{

			exgcd(M,m[i],d,x,y);

			if((r[i]-R)%d)

			{

				fl=1;

				break;

			}

			x=(r[i]-R)/d*x%(m[i]/d);

			R=R+M*x;

			M=M/d*m[i];

			R=R%M;

		}

		if(fl)

			puts("-1");

		else

			printf("%lld\n",(R+M)%M);

	}

	return 0;

}

巴特西

poj 2891 Strange Way to Express Integers【扩展中国剩余定理】

最新文章

热门文章