【模板】exCRT（扩展中国剩余定理）

题目：POJ2891

算法过程：exCRT

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#define int long long
using namespace std;

const int Max=1000010;
int k,x,y,gcd;
int a[Max],m[Max];

inline int get_int()
{
	int x=0,f=1;
	char c;
	for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
	if(c=='-') {f=-1;c=getchar();}
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	return x*f;
}

inline void exgcd(int a,int b)
{
	if(!b) x=1,y=0,gcd=a;
	else
	{
	  exgcd(b,a%b);
	  int t=x;
	  x=y;
	  y=t-a/b*x;
	}
}

inline int solve()
{
	int pa=a[1],pm=m[1];
	for(int i=2;i<=k;i++)
	{
	  exgcd(pm,m[i]);
	  if((a[i]-pa)%gcd) return -1;
	  x=(x*(a[i]-pa)/gcd%m[i]+m[i])%m[i];
	  pa=x*pm+pa;
	  pm=pm*m[i]/gcd;
	  pa=(pa%pm+pm)%pm;
	}
	return pa;
}

signed main()
{
	while(~scanf("%d",&k))
	{
	  for(int i=1;i<=k;i++) m[i]=get_int(),a[i]=get_int();
	  cout<<solve()<<"\n";
	}
	return 0;
}