同余模算术.cpp

数值计算的例子和参考书籍

int Gcd(int a, int b)
{
	return b == 0 ? a : Gcd(b, a % b);
}

/************************************************************
extended euclid algorithm to calculate the gcd(a, b), as well
 as the integer x and y where gcd(a, b) = a * x + b * y.
************************************************************/
int Extend_euclid(int a, int b, int &x, int &y)
{
	int t, d;
	if(b == 0) {x = 1; y = 0; return a;}
	d = Extend_euclid(b, a % b, x, y);
	t = x;
	x = y;
	y = t - a / b * y;
	return d;
}

/********************************************
求解模线性方程 a * x = b (mod n), n > 0
*********************************************/

void modular_linear_equation_solver(int a, int b, int n)
{
	int i, e, d, x, y;
	d = Extend_euclid(a, n, x, y);
	if(b % d > 0) printf("No answer!\n");
	else
	{
		e = (x * (b / d)) % n;
		for(i = 0; i < d; i++)  //notice! here x maybe < 0
			printf("The %dth answer is : %d\n", i + 1, (e + i * (n / d)) % n);
	}
}

/*********************************************
求解模线性方程组(中国余数定理)
a = Bi (mod Wi)
其中W, B已知,Wi > 0且Wi与Wj互质,求a.
*********************************************/
int China(int *B, int *W, int k)
{
	int i, d, x, y, ans = 0, m, n = 1;
	for(i = 0; i < k; i++)
		n *= W[i];
	for(i = 0; i < k; i++)
	{
		m = n / W[i];
		d = Extend_euclid(W[i], m, x, y);
		ans = (ans + y * m * B[i]) % n;
	}
	if(ans > 0) return ans;
	else return ans + n;
}