(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 î
|