中國剩餘定理 模闆

http://blog.csdn.net/xiaotaoqibao/article/details/5781131

參考網址

 一個小知識點 也記下來

如果整數 a 除以整數 b 的餘數是 1，那麼 a 的 2 倍，3 倍，4 倍……b-1 倍除以 b 的餘數

分别是 1*1，2*1，3*1，4*1，......和(b-1)*1。

　　例如：15÷7=2……餘1，那麼：

　　2*15÷7=4……餘 2 (=2*1)

　　3*15÷7=6……餘 3 (=3*1)

　　4*15÷7=8……餘 4 (=4*1)

　　……

　　6*15÷7=12……餘 6 (=6*1)

#include <iostream>
using namespace std;

int Extended_Euclid(int a,int b,int &x,int &y)    //擴充歐幾裡得算法
{
	int d;
	if(b==0)
	{
		x=1;y=0;
		return a;
	}
	d=Extended_Euclid(b,a%b,y,x);
	y-=a/b*x;
	return d;
}

int Chinese_Remainder(int a[],int w[],int len)    //中國剩餘定理  a[]存放餘數  w[]存放兩兩互質的數
{
	int i,d,x,y,m,n,ret;
	ret=0;
	n=1;
	for (i=0;i<len;i++)
		n*=w[i];
	for (i=0;i<len;i++)
	{
		m=n/w[i];
		d=Extended_Euclid(w[i],m,x,y);
		ret=(ret+y*m*a[i])%n;
	}
	return (n+ret%n)%n;
}


int main()
{
	int n,i;
	int w[15],b[15];
	while (scanf("%d",&n),n)   
	{
		for (i=0;i<n;i++)
		{
			scanf("%d%d",&w[i],&b[i]);
		}
		printf("%d/n",Chinese_Remainder(b,w,n));
	}
	return 0;
}