int gcd(int x,int y)
{
   return y==0?x:gcd(y,x%y);
}
有人能解译一下吗？

假定 x=4 y=15
1：x=y=15,y=x%y=4//小值变成除数
2：x=y=4,y=x%y=3//先除小的数然后继续向
3：x=y=3,y=x%y=1
4: x=y=1,y=3%1=0
return x=1

x=3 y=15
1:x=y=15,y=x%y=3
2:x=3 y=0
return x=3

辗转相除法：辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。

谢谢你的讲解

最近看到很多解
ax+by==c这类的~

其实也可以用辗转相除法的思想实现~

举个例子就明白了~

例如求解

39x+17y==10001

用辗转相除法~

+a+0=39   
+0+b=17
+a-2b=5
-3a+7b=2
7a-16b=1
-17a-39b=0

这里可以得到
gcd(39,17)=1

可以看出t*(39*7-17*16)==t

10001%gcd(39,17)==0

所以该方程存在整数解

39*(7*10001)-17*(16*10001)==10001

如果x取最少正整数
那么
x=(7*(10001%17))%17=1
y=(10001-1*39)/17=586

所以
x=1,y=586是这个方程的一个特解

通解为
{
    x=1+17t
    y=(10001-39*(1+17t))/17
}

化简一下就是
{
    x=1+17t
    y=586-39t
}

下面这个代码可以得到这个不定方程的通解

#include<stdio.h>
#include<assert.h>

int main( void )
{
    int i=0;
    
    const int a=39;
    const int b=17;
    
    for (i=0;i!=30;++i)
    {
        assert(39*(1+17*i)+17*(586-39*i)==10001);

        printf("39*(%-4d)+17*(%-4d)=10001\n",1+17*i,586-39*i);
    }
    
    return 0;
}

拓展一下,其实"剩余定理"实质就是一个不定方程(组),当时我看某方法就是怎么配个常数n,当时怎么也看不出一个所以然出来,然后用辗转相除法就容易理解多了,当然如果是3组(多组)数据则算出一组后把参数代入消元再继续算下一组就是了~

[此贴子已经被作者于2018-4-19 21:18编辑过]

额二元一次方程有无数个解  他在坐标系中是一条直线

二元一次方程组才有唯一解；

忘记说的是整数解了~