글 읽기 - 90%에서 틀렸습니다 반례부탁드려요

jms020820 1년 전 0

확장된 유클리드 써서 일반해 범위 구해서 개수 구했고

c언어는 정수형 소수점을 버림하니 부등호 뒷쪽이 양수면 +1 앞쪽이 음수면 -1해서

정수범위 구했습니다.

ex -5.5<= x =< -2.1 -> -5<= x =<-2 -> -5<= x=<-3

0.5<= x =< 6.4 -> 0<=x=<6 -> 1<=x=<6

90퍼에서 틀렸습니다 떴어요 ㅠㅜ

반례찾아주시면 감사하겠습니다.

#include <stdio.h>
#include <stdlib.h>

typedef struct solution {
  long long x, y, gcd;
} sol;
typedef struct div {
  long long per, sol;
} divi;
divi div_(long long a, long long b) {
  if ((a > 0 && b > 0) || (a > 0 && b < 0) || a % b == 0) {
    divi k;
    k.per = a % b;
    k.sol = a / b;
    return k;
  } else if (b > 0) {
    divi k;
    k.per = a % b + b;
    k.sol = a / b - 1;
    return k;
  } else if (b < 0) {
    divi k;
    k.per = a % b - b;
    k.sol = a / b + 1;
    return k;
  }
}
sol Euclid(int a, int b) {
  long long s1 = 1, s2 = 0, t1 = 0, t2 = 1;
  while (b != 0) {
    divi tmp = div_(a, b);
    long long tmp_r = tmp.per, ans = tmp.sol, tmp_s = s2, tmp_t = t2;
    a = b;
    b = tmp_r;
    s2 = s1 - s2 * ans;
    s1 = tmp_s;
    t2 = t1 - t2 * ans;
    t1 = tmp_t;
  }
  sol ret;
  if (a < 0) {
    ret.gcd = -a;
  } else {
    ret.gcd = a;
  }
  ret.x = s1;
  ret.y = t1;
  return ret;
}
int main() {
  int a, b, c, x1, x2, y1, y2;
  scanf("%d%d%d", &a, &b, &c);
  scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
  if (x1 > x2 || y1 > y2) {
    printf("0");
    return 0;
  }
  if (a == 0 && b == 0 && c == 0) {
    printf("%lld", (long long)(x2 - x1 + 1) * (y2 - y1 + 1));
    return 0;
  } else if (a == 0 && b == 0) {
    printf("%d", 0);
    return 0;
  } else if (a == 0 || b == 0) {
    if (a != 0 && c % a == 0) {
      if (-c / a >= x1 && -c / a <= x2) {
        printf("%d", y2 - y1 + 1);
      } else {
        printf("0");
      }
      return 0;
    } else if (b != 0 && c % b == 0) {
      if (-c / b >= y1 && -c / b <= y2) {
        printf("%d", x2 - x1 + 1);
      } else {
        printf("0");
      }
      return 0;
    } else {
      printf("0");
      return 0;
    }
  } 
  sol euc = Euclid(a, b);
  long long gcd = euc.gcd;
  if ((-c) % gcd != 0) {
    printf("%d", 0);
    return 0;
  }
  long long ans_x = euc.x * (-c) / gcd;
  long long ans_y = euc.y * (-c) / gcd;
  long double comx1 = gcd / (double)b * (x1 - ans_x);
  long double comx2 = gcd / (double)b * (x2 - ans_x);
  long double comy1 = gcd / (double)a * (ans_y - y1);
  long double comy2 = gcd / (double)a * (ans_y - y2);
  long double topx, botx, topy, boty;
  if (comx1 >= comx2) {
    topx = comx1;
    botx = comx2;
  } else {
    topx = comx2;
    botx = comx1;
  }
  if (comy1 >= comy2) {
    topy = comy1;
    boty = comy2;
  } else {
    topy = comy2;
    boty = comy1;
  }
  long long topxt = topx, botxt = botx, topyt = topy, botyt = boty;
  if (topx < 0) 
    topxt--;
  if (botx > 0) 
    botxt++;
  if (topy < 0)
    topyt--;
  if (boty > 0)
    botyt++;
  if (topxt < botyt || topyt < botxt) {
    printf("0");
    return 0;
  }
  long long realtop, realbot;
  if (botxt <= botyt) {
    realbot = botyt;
  } else {
    realbot = botxt;
  }
  if (topxt >= topyt)
    realtop = topyt;
  else
    realtop = topxt;
  printf("%lld", realtop - realbot + 1);
  return 0;
}

jms020820 1년 전 0

Ax +By = c 계산할 때 B가 음수이고 A%B == 0 일 때는 gcd를 음수처리해야 정상적인 답이나오네요....

gcd는 무조건 양수처리했는데 이것때문에 틀렸습니다

참고하세요 ㅠㅜ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

90%에서 틀렸습니다 반례부탁드려요

jms020820 1년 전 0

jms020820 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말