2012年计算机等级二级C++辅导实例编程（3）

　两个数论的算法

　　#include

　　using namespace std;

　　struct result

　　{

　　int d;

　　int x;

　　int y;

　　};

　　//d=gcd(a,b)=ax+by

　　result ExtendeEuclid(int a,int b)

　　{

　　result res;

　　if(!b)

　　{

　　res.d=a;

　　res.x=1;

　　res.y=0;

　　return res;

　　}

　　result temp=ExtendeEuclid(b,a%b);

　　res.d=temp.d;

　　res.x=temp.y;

　　res.y=temp.x-a/b*temp.y;

　　return res;

　　}

　　inline long mod(long a,long b)

　　{

　　return (a%b+b)%b;

　　}

　　//计算满足ax和b关于n同余的x

　　void ModularLinearEquationSolver(int a,int b,int n)

　　{

　　if(a<=0||n<=0)

　　{

　　cout<<"参数有错"<

　　return ;

　　}

　　result re=ExtendeEuclid(a,n);

　　if(b%re.d==0)

　　{

　　int x0=mod(re.x*(b/re.d),n);

　　for(int i=0;i<=re.d-1;i++)

　　{

　　cout<

　　}

　　}

　　else

　　{

　　cout<<"无解"<

　　}

　　}

　　int main()

　　{

　　ModularLinearEquationSolver(14,30,100);

　　return 0;

　　}