UVA 10367 - Equations(数论+模拟）

题目链接：10367 - Equations

思路：模拟。。。恶心题。。很多细节要注意

代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 0x3f3f3f3f
int t;
char str[1005];
struct Exp {
    long long x, y, c;
    Exp() {x = 0; y = 0; c = 0;}
} e[2];

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Exp tra(char *str) {
    Exp ans;
    int n = strlen(str);
    long long sum = 0, flag = 1, f = 1;
    str[n] = ‘ ‘;
    for (int i = 0; i <= n; i++) {
	if (str[i] == ‘=‘) {
	    f = -1;
	    continue;
	}
	if (str[i] >= ‘0‘ && str[i] <= ‘9‘) {
	    sum = sum * 10 + str[i] - ‘0‘;
	}
	else if (str[i] == ‘-‘)
	    flag = -flag;
	else if (str[i] == ‘+‘)
	    flag = 1;
	else if (str[i] == ‘x‘) {
	    if (sum == 0) sum = 1;
	    ans.x += f * flag * sum;
	    sum = 0;
	    flag = 1;
	}
	else if (str[i] == ‘y‘) {
	    if (sum == 0) sum = 1;
	    ans.y += f * flag * sum;
	    sum = 0;
	    flag = 1;
	}
	else {
	    if (sum != 0) {
		ans.c -= f * flag * sum;
		sum = 0;
		flag = 1;
	    }
	}
    }
    return ans;
}

void init() {
    memset(e, 0, sizeof(e));
    getchar();
    gets(str);
    e[0] = tra(str);
    gets(str);
    e[1] = tra(str);
}

struct Ans {
    long long zi, mu, f, vis;
    void init() {
	zi = 0; mu = 0; f = 1; vis = 0;
    }
    void tra() {
	if (zi < 0) {
	    zi = -zi;
	    f *= -1;
	}
	if (mu < 0) {
	    mu = -mu;
	    f *= -1;
	}
	long long g = gcd(zi, mu);
	if (g != 0) {
	    zi /= g; mu /= g;
	}
    }
    void put() {
	if (vis) printf("don‘t know\n");
	else if (zi == 0) printf("0\n");
	else if (mu == 1) printf("%lld\n", f * zi);
	else printf("%lld/%lld\n", f * zi, mu);
    }
} ansx, ansy;

void solve() {
    ansx.init(); ansy.init();
    int g0 = gcd(gcd(abs(e[0].x), abs(e[0].y)), abs(e[0].c));
    int g1 = gcd(gcd(abs(e[1].x), abs(e[1].y)), abs(e[1].c));
    if (g0 != 0) {
	e[0].x /= g0; e[0].y /= g0; e[0].c /= g0;
    }
    if (g1 != 0) {
	e[1].x /= g1; e[1].y /= g1; e[1].c /= g1;
    }
    ansx.zi = e[0].c * e[1].y - e[1].c * e[0].y;
    ansx.mu = e[0].x * e[1].y - e[1].x * e[0].y;
    ansy.zi = e[0].c * e[1].x - e[1].c * e[0].x;
    ansy.mu = e[0].y * e[1].x - e[0].x * e[1].y;
    ansx.tra();
    ansy.tra();
    if (e[0].x == 0 && e[0].y == 0 && e[0].c != 0) {
	ansx.vis = 1; ansy.vis = 1; return;
    }
    if (e[1].x == 0 && e[1].y == 0 && e[1].c != 0) {
	ansx.vis = 1; ansy.vis = 1; return;
    }
    if (e[0].x == 0 && e[0].y == 0 && e[1].x == 0 && e[1].y == 0) {
	ansx.vis = 1; ansy.vis = 1; return;
    }
    if (e[0].x == 0 && e[1].x == 0) {
	ansx.vis = 1;
	if (e[0].c * e[1].y != e[1].c * e[0].y)
	    ansy.vis = 1;
	else {
	    if (e[0].y != 0) {
		ansy.zi = e[0].c;
		ansy.mu = e[0].y;
	    }
	    if (e[1].y != 0) {
		ansy.zi = e[1].c;
		ansy.mu = e[1].y;
	    }
	    ansy.tra();
	}
	return;
    }
    if (e[0].y == 0 && e[1].y == 0) {
	ansy.vis = 1;
	if (e[0].c * e[1].x != e[1].c * e[0].x)
	    ansx.vis = 1;
	else {
	    if (e[0].x != 0) {
		ansx.zi = e[0].c;
		ansx.mu = e[0].x;
	    }
	    if (e[1].x != 0) {
		ansx.zi = e[1].c;
		ansx.mu = e[1].x;
	    }
	    ansx.tra();
	}
	return;
    }
    if (ansx.mu == 0 && ansy.mu == 0) {
	if (!ansx.vis && !ansy.vis) {
	    ansx.vis = 1;
	    ansy.vis = 1;
	    return;
	}
    }
}

int main() {
    scanf("%d", &t);
    while (t--) {
	init();
	solve();
	ansx.put();
	ansy.put();
	if (t) printf("\n");
    }
    return 0;
}

UVA 10367 - Equations(数论+模拟）,布布扣,bubuko.com

UVA 10367 - Equations(数论+模拟）

原文：http://blog.csdn.net/accelerator_/article/details/23614319