知识点 |
您所在的位置：网站首页 › 不定方程求解c语言代码是什么方法 › 知识点 |
| 找到一个解 O ( l o g n ) O(logn) O(logn) 对ab使用扩展gcd得到 g , x g , y g g ,x_g, y_g g,xg,yg a x g + b y g = g a x_g + b y_g =g axg+byg=g 如果 g ∣ c g|c g∣c,则有解。两边乘 c g \frac{c}{g} gc a ⋅ x g ⋅ c g + b ⋅ y g ⋅ c g = c a \cdot x_g \cdot \frac{c}{g} + b \cdot y_g \cdot \frac{c}{g} = c\\ a⋅xg⋅gc+b⋅yg⋅gc=c 得到一组特解 x 0 = x g ⋅ c g y 0 = y g ⋅ c g . x_0 = x_g \cdot \frac{c}{g}\\ y_0 = y_g \cdot \frac{c}{g}. x0=xg⋅gcy0=yg⋅gc. int gcd(int a, int b, int &x, int &y) { if (a == 0) { x = 0; y = 1; return b; } int x1, y1; int d = gcd(b%a, a, x1, y1); x = y1 - (b / a) * x1; y = x1; return d; } bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g) { g = gcd(abs(a), abs(b), x0, y0); if (c % g) { return false; } x0 *= c / g; y0 *= c / g; if (a int x, y, g; if (!find_any_solution(a, b, c, x, y, g)) return 0; a /= g; b /= g; int sign_a = a > 0 ? +1 : -1; int sign_b = b > 0 ? +1 : -1; shift_solution(x, y, a, b, (minx - x) / b); if (x maxx) return 0; int lx1 = x; shift_solution(x, y, a, b, (maxx - x) / b); if (x > maxx) shift_solution(x, y, a, b, -sign_b); int rx1 = x; shift_solution(x, y, a, b, -(miny - y) / a); if (y maxy) return 0; int lx2 = x; shift_solution(x, y, a, b, -(maxy - y) / a); if (y > maxy) shift_solution(x, y, a, b, sign_a); int rx2 = x; if (lx2 > rx2) swap(lx2, rx2); int lx = max(lx1, lx2); int rx = min(rx1, rx2); if (lx > rx) return 0; return (rx - lx) / abs(b) + 1; } 找到x+y最小的解将通解带入 x + y x+y x+y x ′ + y ′ = x + y + k ⋅ ( b g − a g ) = x + y + k ⋅ b − a g x' + y' = x + y + k \cdot \left(\frac{b}{g} - \frac{a}{g}\right) = x + y + k \cdot \frac{b-a}{g} x′+y′=x+y+k⋅(gb−ga)=x+y+k⋅gb−a If a ; b a ; b ab, 找最大的 k k k. If a = b a = b a=b, x + y x + y x+y为定值. |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |