再说中国剩余定理、扩展欧几里德和同余方程组

int gcd(int a,int b)  
{  
    if(b==0)return a;  
   
    else return gcd(b,a%b);  
 }

int Egcd(int a,int b,int& x,int& y)
{
	int d,t;
	if(!b)
	{
		x=1;y=0;return a;
	}
	else
	{
		Egcd(b,a%b,y,x);
		y-=x*(a/b);
	}

}

mf求法：如果理解了扩展欧几里得 ax+by=d, 就可以想到:
                     mi*mf  mod ni = 1 => mi*mf+ni*y=1;

对于这个式子 mi*mf+ni*y=1应该很熟悉吧，没错，就是用Egcd来求mf！

①：mi，②：ni，③：mf，④：y，不是想要mf吗？！把它放到③吧！

接下来就很简单了吧，看代码：

for(i=0;i<n;i++)
			s*=a[i];
		for(i=0;i<n;i++)
		{
			m=s/a[i];<span style="white-space:pre">			</span>//m表示mi
			gcd(m,a[i],x,y);
			x=(x%a[i]+a[i])%a[i];
			sum=(sum+m*b[i]*x%s)%s;<span style="white-space:pre">			</span>//这里换做用bi表示余数
		}

#include <stdio.h>
#include <string.h>
#include <math.h>
typedef __int64 int64;				//这里要用64位

int64 a[11],b[11];
int64 Egcd(int64 a,int64 b,int64& x,int64& y)
{
	int64 d,t;
	if(!b)
	{
		x=1;y=0;return a;
	}
	else
	{
		Egcd(b,a%b,y,x);
		y-=x*(a/b);
	}

}

int main()
{
	int64 sum,m,s,x,y;
	int n,i;
	while(scanf("%d",&n)!=EOF)
	{
		sum=0;s=1;
		for(i=0;i<n;i++)
			scanf("%I64d %I64d",&a[i],&b[i]);
		for(i=0;i<n;i++)
			s*=a[i];
		for(i=0;i<n;i++)
		{
			m=s/a[i];
			Egcd(m,a[i],x,y);
			x=(x%a[i]+a[i])%a[i];
			sum=(sum+m*b[i]*x%s)%s;
		}
		printf("%I64d\n",sum);					//既然要用64位，那输入输出也要用%I64d，否则用%d提交也会WA的。。。。
	}
	return 0;
}