2015年计算机等级考试二级Ｃ++辅导讲义（3）
发布时间：2012/5/17 16:48:01 来源：城市网学院 编辑：ziteng
两个数论的算法
#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)
{ [NextPage] 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;
}
