// Algorithm.cpp: implementation of the CAlgorithm class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "Algorithm.h"
#include
#include
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
#define bigint __int64
CAlgorithm::CAlgorithm()
{
result_x = 0; //初始化
result_n = 0;
}
/******************************************************
//根据欧几里德（辗转相除）算法求两个数的最大公约数
//函数返回a、b的最大公约数
//选择迭代或递归方法完成
/******************************************************
/*************************************
迭代方法
***************************************/
/*int CAlgorithm::Greatest_Common_Divisor( int a,int b )
{
while (b!=0)
{
int temp=b;
b=a%b;
a=temp;
}
return a; //余数r=0那一步的除数
}*/
/***************************************
递归方法
***************************************/
int CAlgorithm::Greatest_Common_Divisor(int a, int b)
{
int r,q;
do
{
q=a/b;
r=a-q*b;
a=b;
b=r;
}while(r!=0);
return a ;
}
/*****************************************************************
//利用两个数最大公约数与最小公倍数乘积和两数乘积的关系求最小公倍数
//函数返回a、b的最小公倍数
*****************************************************************/
int CAlgorithm::Least_Common_Multiple ( int a,int b )
{
int Product=a*b;
while (b!=0)
{
int temp=b;
b=a%b;
a=temp;
}
return Product/a;
}
/*****************************************************************
//由相关定理、引理知：gcd(a,b)=gcd(b,a%b)=xa+yb
//当gcd(a,b)=1时，a模b的逆存在且唯一
//同时gcd(a,b)=1=xa+yb中a的系数x即为a模b的逆
//要求以下函数使用递归方法返回a模b的逆
//需要掌握的技巧：函数“值传递”与“引用传递”的不同
*****************************************************************/
int CAlgorithm::Extended_GCD(int a,int b,int &gcd,int &x, int &y )
{
//请补充代码
if(gcd==1)
return ( x + b ) % b;
else
return -9999;
}
/*******************************************************************************************************
//形如 x ≡ ai的线性同余方程组,若m[i]两两互素则方程组有解，以所有模数乘积取模，解唯一
令mm=m[0]*m[1]*....m[FuncNum-1]
通过调用Extended_GCD函数求解每一个方程中M[i]模m[i]的逆，用y[i]表示
根据中国余数定理求解方程组在0-mm之间的唯一解
参数解释：FuncNum代表方程个数，数组a[], m[]与方程x ≡ ai的系数分别对应
******************************************************************************************************/
void CAlgorithm::solModularEquations( int FuncNum,int a[],int m[])
{
int i, j;
int mm=1,x=0;// x用于存放求和结果
int M[100], y[100];
int gcd1, x1, y1; // Extended_GCD的实参
IsCoprime = true; //互素标志，初始化为true
// (1)判断方程组中的模m[i]是否两两互素
for ( i=0; i<FuncNum-1; i++ )
{
for ( j=i+1; j<FuncNum; j++ )
{
if ( /*////////////////////////////*/ )
continue;
else
{
IsCoprime = false; //不是两两互素，令IsCoprime为false
return;
}
}
}
// (2) 运用中国剩余定理求x的值
//请补充代码
result_x = x%mm;//用于从界面输出方程组在0-mm之间的唯一解
result_n = mm; //用于从界面输出所有模数的乘积
}
