SGU 106 模线性方程

2019-04-13 17:29发布

站内文章 / 模拟电子
17286 0 1207
一气之下变量全变成__int64就A了，不知道为什么要会越界。
先考虑一些特殊情况。
其它情况解两个方程组即可
x1 <= x0 + k*a <= x2;
 y1 <= y0 - k*b <= y2; 求出来的k值取相交部分。
#include #include #include #include using namespace std; #define LL __int64 // x1 = y2, y1 = x2 - (a/b) * y2; LL ex_gcd(LL a, LL b, LL &x, LL &y) { if (!b) { x = 1; y = 0; return a; } LL t = ex_gcd(b, a % b, x, y); LL xx = x; x = y; y = xx - a / b * y; return t; } int main() { LL i; int cas; LL a, b, c, x, y, x1, x2, y1, y2; cin >> a >> b >> c >> x1 >> x2 >> y1 >> y2; if (a < 0) a = -a, b = -b; else c = -c; if (!a && !b && c) { puts("0"); return 0; } if (!a && !b && !c) { printf("%I64d", (x2 - x1 + 1) * (y2 - y1 + 1)); return 0; } if (!a && b) { LL ty = c / b; if (c % b == 0 && ty >= y1 && ty <= y2) printf("%I64d ", (x2 - x1 + 1)); else puts("0"); return 0; } if (a && !b) { LL tx = c / a; if (c % a == 0 && tx >= x1 && tx <= x2) printf("%I64d ", (y2 - y1 + 1)); else puts("0"); return 0; } LL t = ex_gcd(a, b, x, y); if (c % t != 0) { puts("0"); return 0; } a /= t; b /= t; c /= t; x *= c; y *= c; // printf("a = %d b = %d c = %d x = %d y = %d ", a, b, c, x, y); LL l1, r1; x1 -= x; x2 -= x; if (b < 0) { b = -b; x1 = -x1; x2 = -x2; swap(x1, x2); } if (x1 >= 0) l1 = (x1 + b - 1) / b; else l1 = x1 / b; if (x2 >= 0) r1 = x2 / b; else { LL t = x2 / b; LL tp = x2 - t * b; if (tp < 0) t--; r1 = t; } LL l2, r2; y1 -= y; y2 -= y; y1 = -y1; y2 = -y2; swap(y1, y2); if (a < 0) { a = -a; y1 = -y1; y2 = -y2; swap(y1, y2); } if (y1 >= 0) l2 = (y1 + a - 1) / a; else l2 = y1 / a; if (y2 >= 0) r2 = y2 / a; else { LL t = y2 / a; LL tp = y2 - t * a; if (tp < 0) t--; r2 = t; } // printf("l1 = %d r1 = %d l2 = %d r2 = %d ", l1, r1, l2, r2); l1 = max(l1, l2); r1 = min(r1, r2); if (l1 > r1) puts("0"); else printf("%I64d ", r1 - l1 + 1); return 0; }

热门文章