chrt.cpp

中国剩余定理的C程序实现

// 演示中国剩余定理
// 本程序可以从3个方程推广到更多个方程
// 谁要是能把该程序推广到n个方程的情况，请给我发mail.
//    [e-mail]  2003 12 9


/* 如果推广到n个方程的提示
   a1,a2,a3可以使用一个数组a[10], 则可以推广到10个方程的情况
   同样，m1,m2,m3也使用一个数据m[10]
         M1,M2,M3也使用一个数据M[10]
		 y1,y2,y3也使用一个数据y[10]
   然后，后面的运算就需要相应的使用一个for循环即可
*/

#include <stdio.h>
#include <stdlib.h>

void usage()
{
	puts("chrt <m1> <a1> <m2> <a2> <m3> <a3>");
	puts("  m1,m2,m3是模，a1,a2,a3是余数, 即:");
	puts("  x ≡ a1 mod m1");
	puts("  x ≡ a2 mod m2");
	puts("  x ≡ a3 mod m3");
	exit(-2);
}

// 求 a mod m 的逆元，即求b满足ab≡1 mod m
int reverse(int a, int m)
{
	int b, b1=1, b2=0;  // 逆元
	int r, r1=a, r2=m;  //	

	do {
		r = r2 % r1;   //  y-kx = r
		b = (b2-(r2/r1)*b1)%m;
		r2 = r1;	b2 = b1;
		r1 = r;		b1 = b;
	} while (r>1);
	
	if (r==0) // 如果r＝0，则r1中就是gcd，如果想要的话也可以带走
		return 0;
	if (b<0)
		b += m;
	return b;
}


main(int argc, char* argv[])
{
/*
	x ≡ a1 mod m1
	x ≡ a2 mod m2
	x ≡ a3 mod m3
*/
	int a1,a2,a3;   // 余数         
	int m1,m2,m3;   // 模
	int M1,M2,M3;   // 模的对偶
	int y1,y2,y3;   // y1=M1 mod m1 的逆元，。。。
	int M;          // 模
    int x;			// 解	

	if (argc!=7)
		usage();

	if (sscanf(argv[1], "%d", &m1)!=1) usage();
	if (sscanf(argv[2], "%d", &a1)!=1) usage();

	if (sscanf(argv[3], "%d", &m2)!=1) usage();
	if (sscanf(argv[4], "%d", &a2)!=1) usage();

	if (sscanf(argv[5], "%d", &m3)!=1) usage();
	if (sscanf(argv[6], "%d", &a3)!=1) usage();

	M = m1*m2*m3;
	M1 = M/m1;
	M2 = M/m2;
	M3 = M/m3;
	
	y1 = reverse(M1, m1);
	y2 = reverse(M2, m2);
	y3 = reverse(M3, m3);
   
	if ((y1==0) || (y2==0) || (y3==0))
	{
		puts("有错！可能是参数错");
		usage();
	}

	printf("梅花数组 %d %d %d\n", M1*y1 % M, M2*y2 % M, M3*y3 % M);
	x = a1*M1*y1 + a2*M2*y2 + a3*M3*y3;
	x = x % M;

	if ((x%m1 != a1) ||
		(x%m2 != a2) ||
		(x%m3 != a3))
	{
		puts("有错！可能是参数错");
		usage();
	}

	printf("方程：\n");
	printf("     x ≡ %d mod %d\n", a1, m1);
	printf("     x ≡ %d mod %d\n", a2, m2);
	printf("     x ≡ %d mod %d\n", a3, m3);
	printf(" 的解是 x ≡ %d mod %d\n", x, M);
	printf(" 中间M1,M2,M3是%d, %d, %d\n", M1, M2, M3);
    printf("     y1,y2,y3是%d, %d, %d\n", y1, y2, y3);
	return 0;
}