binteuclidean.h

一个很好用的大整数的类, 最大可支持9999990位的十进制整数

// BIntEuclidean.h: interface for the CBIntEuclidean class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_BINTEUCLIDEAN_H__3B77102E_DC8A_424C_89A6_14E56BAA9955__INCLUDED_)
#define AFX_BINTEUCLIDEAN_H__3B77102E_DC8A_424C_89A6_14E56BAA9955__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "PrimeTest.h"

class __declspec(dllexport) CBIntEuclidean  
{
public:
	CBIntEuclidean();
	virtual ~CBIntEuclidean();

public:
	static void gcd(CZBInt &cA, CZBInt &cB, CZBInt &cGcd);
				//计算cA和cB的最大公因数cGcd,如果其中之一为0,则cGcd=0
	static void extend(CZBInt &cA, CZBInt &cB, CZBInt &cGcd,
						CZBInt &cX, CZBInt &cY);//
				//扩展的Euclidean算法,算出d=gcd(a,b)和满足等式ax+by=d的整数x和y
				//X和A相配, Y和B相配,不论A,B哪个大
				//X, Y可能为负
	static void lcm(CZBInt &cA, CZBInt &cB, CZBInt &cGcd,
					CZBInt &cLcm);//根据最大公因数求最小公倍数
				//cGcd是cA和cB的最大公因数, cLcm是返回的cA和cB的最小公倍数

	//中国剩余定理:令r个整数m1,m2,...,mr两两互素, a1,a2,...,ar是任意r个整数,
	//则同余方程组 x = ai mod mi, 1<=i<=r, 模M=m1*m2*...*mr有唯一解
	//x = ai*Mi*yi, 其中Mi=M/mi, yi=Mi^-1 mod mi
	static int CnOverPlus(CZBInt *puM, CZBInt *puA, UINT uR, CZBInt &uX);//根据中国剩余定理求解同余方程组
		//puM:存放各个mi, puA:存放各个ai, uR:r,即数组的长度, uX:结果
		//返回0:代表成功, -1:puM不是两两互素, -2:puM中有0, -3:其他错误(uR<=1)
};

#endif // !defined(AFX_BINTEUCLIDEAN_H__3B77102E_DC8A_424C_89A6_14E56BAA9955__INCLUDED_)