2017九山顶农家院价格:C语言有关方程的问题，高手指教

求解二元一次不定方程

求解二元一次不定方程
我们的任务是解二元一次不定方程
ax+by=c (*)
其中a,b,c都是整数,所求的解(x,y)也是整数.
由于方程(*)如果有解,则解不是唯一确定的,所以称为不定方程.二元一次不定方程是一类重要的方程,应用很广.关于方程(*)的可解性,有下面的两个重要的结论:
(1)设gcd(a,b)表示整数a,b的最大公约数.方程(*)有解的充分必要条件是gcd(a,b)|c.(记号“x|y”表示x能整除y，即存在整数k,使y=kx).
(2)如果(x0,y0)是方程(*)的一组解，则对任何整数t,(x0+bt,y0-at)也都是方程(*)的解.
许多讲数论的书都对这两个结论做了严格的论证.
下面我们讨论具体求解的方法.
为了避免计算中对负数和0的讨论,我们假定a>0,b>0,并且a>=b.
假定方程(*)有解,即系数满足：gcd(a,b)|c,这时,c’=c/gcd(a,b)一定是个整数.我们先讨论下面的方程:
ax+by=f (**)
其中f=gcd(a,b),右端项恰好是左边两系数的最大公因子.
显然,如果(x0,y0)是方程(**)的一组解,则(c’x0,c’y0)也是方程(*)的一组解,即a(c’x0)+b(c’y0)=(c’f)=c.
在方程(**)中,取a=107,b=73,c=1,显然满足gcd(107,73)=1,方程
107x+73y=1 (***)
有解.我们用类似于求最大公约数的辗转相除的方法求这个解.利用辗转相除,可以得到:
107=73+1+34,
73=34*2+5,
34=5*6+4,
5=4*1+1,
4=1*4.
写成一般的形式:si=ti*qi+ri,
qi=si/ti,ri=si%ti,si+1=ti,ti+1=ri.
认真分析上面的规律,可以归纳出具体的求解方法.我们先用下面的表格列出相应的关系:
在下表中,i为辗转计算的次数.q[i]=s[i]/t[i]为相除得到的商.表中没有列出r[i],它就是后一列的t[i].

i 0 1 2 3 4(end) 5
s[i] 107 73 34 5 4
t[i] 73 34 5 4 1 0
q[i] 1 2 6 1 4
x[i] 0 1 2 13 15
y[i] 1 q[0]=1 3 19 22
表14-1
关键算法是x[k],y[k]的递推计算公式:
x[0]=0,x[1]=1; x[i+1]=x[i]*q[i]+x[i-1],当i>1时.
y[0]=1,y[1]=q[0]; y[i+1]=y[i]*q[i]+y[i-1],当i>1时.
当t[k]≠0且r[k]=s[k]%t[k]=0时,k就是最后一轮计算,这时,
x[k]=15,y[k]=22就是所要的结果,但要加上适当的符号后,才能得到原方程的解(x,y):
x=(-1)k-1x[k],y=(-1)ky[k].
关于x[i],y[i]的递推公式的推导较烦琐,就不在这里介绍了.
对于方程(***),用这种方法可以求得x=-15,y=22,显然,107*(-15)+73*22=1,满足方程.
程序:
#include <stdio.h>
void result_one(int a,int b,int c,int *x2,int *y2)
[code]/* 函数1:计算不定方程的一组解 */
{int q[200],x[200],y[200];
int d1,d2,i,r,t,j,gcd;
x[0]=0;y[0]=1;
d1=a;d2=b;
for(i=0;i<200;i++)
{q[i]=d1/d2;
r=d1%d2; d1=d2;d2=r;
if(r==0)
{gcd=d1; break;
}
if(i==0)
{x[1]=1; y[1]=q[0];
}
else
{x[i+1]=q[i]*x[i]+x[i-1];
y[i+1]=q[i]*y[i]+y[i-1];
}
}
for(t=-1,j=1;j<i;j++) t=-t;
*x2=-t*x[i];
*y2=t*y[i];
/* 以上求方程ax+by=gcd(a,b)的一组解 */
if(c%gcd!=0)
{printf("No solution!\n");
exit(0);
}
t=c/gcd;
*x2=*x2*t; *y2=*y2*t;
/* 以上求方程ax+by=c的一组解 */
}
void test1(int a,int b,int c,int x,int y)
/* 函数2:检验解的正确性 */
{if(a*x+b*y==c)
printf("Ok!\n");
else
printf("Result error!\n");
}
main()
/* 函数3:主函数 */
{int a,b,c,x2,y2;
printf("Input a(>0),b(>0),c:\n");
scanf("%d%d%d",&a,&b,&c);
result_one(a,b,c,&x2,&y2);
test1(a,b,c,x2,y2);
printf("x=%d y=%d \n",x2,y2);
}[/code]

我说说思路吧。
这其实是一个二元一次不定方程。二元一次不定方程有如下结论：
如果x1,y1是方程ax+by+c=0的一个特解的话，那么方程的通解就是：
x=x1+k*b/(a,b);y=y1+k*a/(a,b)
所以说，只要先用枚举把通解找出来，再把(a,b)算出来（用辗转相除法），就可以得到所有解了。
又因为只需要求在某个区域中解的个数，所以可以分别根据x,y的区域得到两个k的范围，然后把两个范围合在一起就可以得到解的个数了。

这个? 不难吧
带入x(x_1,x_2)的界限 求出y(y_1',y_2',y_1'>=y_2')的界限
其中 y_1'不为整数则取整加一 y_2'不为整数则取

所以 y_1''=max(y_1',y_1)<=y<=min(y_2',y_2)=y_2''
然后return y_2''-y_1''+1 就行啦