解不定方程ax＋by＝c!*

(1) 讨论是否有解：如果 c mod gcd(a,b)≠0，那么方程无解。

file:///C:/Users/123/AppData/Local/Temp/ksohtml11960/wps19.png        a        b        c

(2) 转化：方程可变为 a’x＋b’y＝c’，其中a'=        ，b'=        ，c'=         

        gcd(a,b)        gcd(a,b)        gcd(a,b)

在求解之前一定先转化，否则 x、y 可能是错误的。

(3) 求解：和gcd很像。

void exgcd(int a, int b, int c, int &x, int &y) { if (a == 0) {   x = 0;   y = c / b; } else

第十二单元 数论算法

{

  exgcd(b % a, a, c, x, y);   y = x;

  x = (c - b * y) / a;

}

}

ìx＝cx0＋cbk （其中 k∈Z）。 (4) 构造通解：假设 x0，y0是一组解，那么通解为íy＝cy0－cak

î