encliddlg.cpp

欧几里德算法求逆的源代码

// EnclidDlg.cpp : implementation file
//

#include "stdafx.h"
#include "Enclid.h"
#include "EnclidDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif


/////////////////////////////////////////////////////////////////////////////
// CEnclidDlg dialog

CEnclidDlg::CEnclidDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CEnclidDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CEnclidDlg)
	m_na = 2760;
	m_nb = 167;
	m_nc = 1;
	m_ni = 1;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
}

void CEnclidDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CEnclidDlg)
	DDX_Text(pDX, IDC_ED_a, m_na);
	DDX_Text(pDX, IDC_ED_b, m_nb);
	DDX_Text(pDX, IDC_ED_c, m_nc);
	DDX_Text(pDX, IDC_ED_i, m_ni);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CEnclidDlg, CDialog)
	//{{AFX_MSG_MAP(CEnclidDlg)
	ON_BN_CLICKED(IDC_BN_INV, OnBnInv)
	ON_BN_CLICKED(IDC_BN_MAX_FACTOR, OnBnMaxFactor)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CEnclidDlg message handlers

BOOL CEnclidDlg::OnInitDialog()
{
	CDialog::OnInitDialog();
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

/*---------------------------------------------------------------------------------------
函数原型：int MaxFactor(int a,int b)
函数功能：求两输入自然数的最大公约数
作    者：小贝壳儿
日    期：2005-12-8 0:25
说    明：使用了函数递归
----------------------------------------------------------------------------------------*/
int MaxFactor(int a,int b)
{
	if(0==a*b)return 0;

	if(0!=a%b)return MaxFactor(b,a%b);
	return abs(b);
}


/*---------------------------------------------------------------------------------------
函数原型：int EuclidInv(int a,int b)
函数功能：欧几里德(Euclid)算法求b模a的逆元	[b*?=1 mod(a)]
作    者：小贝壳儿
日    期：2005-12-9 17:25
说    明：使用了函数递归
		  推导过程如下：
		  定理：若a与b互素，则有a*s+b*t=1,其中s,t为整数
		  以a=2760,b=167为例
			<2760,167>		1= 1223*167 +	2760*(-74)
			 <167,88>		1=	 93*88	+	 167*(-49)
			  <88,79>		1=	 39*79	+	  88*(-35)
			  <79,9>		1=	 44*9 	+	  79*(-5)
			   <9,7>		1=    4*7 	+	   9*(-3)
			   <7,2>		1=	  4*2 	+	   7*(-1)
			   <2,1>		1=	  1*2 	+	   1*(-1)

函数返回值的递归过程为：
  1-2                    4-7                   4-9                     44-79
1-----(-1)------------>4-----(-3)------------>4----(-5)------------->44------(-35)---------------->
          (1-7*(-1))/2           (1-9*(-3))/7          (1-79*(-5))/9              (1-88*(-35))/79   
___________________________________________________________________________________________________

   39-88                          93-167
39-------(-49)---------------->93--------(-74)------------------->1223
              (1-167*(-49))/88                (1-2760*(-74))/167

----------------------------------------------------------------------------------------*/
int EuclidInv(int a,int b)
{
	if(1!=MaxFactor(a,b))return 0;

	if(1==b)return 1;
	return ((b-EuclidInv(b,a%b))*a+1)/b;
}

void CEnclidDlg::OnBnMaxFactor() 
{
	UpdateData();
	m_nc=MaxFactor(m_na,m_nb);
	UpdateData(0);	
}

void CEnclidDlg::OnBnInv() 
{
	OnBnMaxFactor();
	if(1!=m_nc){
		CString str;
		str.Format("错误：%d与%d必须互素！\n(最大公约数为%d)",m_na,m_nb,m_nc);
		AfxMessageBox(str);
		return;
	}
	m_ni=EuclidInv(m_na,m_nb);
	UpdateData(0);	
}