글 읽기 - 반례찾아주시면 감사하겠습니다

jms020820 1년 전 0

33%에서 틀렸습니다

#include <stdio.h>
#include <stdlib.h>
long long gcd(long long n, long long k) {
  if (k > n) {
    int tmp = k;
    k = n;
    n = tmp;
  }
  while (k != 0) {
    long long tmp = k;
    k = n % k;
    n = tmp;
  }
  if (n < 0) {
    return -n;
  } else {
    return n;
  }
}
int main() {
  unsigned long long a, b, n;
  int q;
  scanf("%lld %lld %lld", &a, &b, &n);
  long long div[10000];
  long long div_back[10000];
  int div_index = 0;
  for (q = 1; q * q <= n; q++) {
    if(n%q==0){
			div[div_index]=q;
			div_back[div_index++] = n/q;
		}
  }
  long long tmp = a * b / gcd(a, b);
  int count_k = 0;
  for (q = 0; q < div_index; q++) {
    long long mem = gcd(tmp, div[q]);
    if (n == tmp * div[q] / mem) {
      printf("%lld", div[q]);
      count_k++;
      return 0;
    }
  }
  for (q = div_index - 1 ; q >= 0; q--) {
    long long meme = gcd(tmp, div_back[q]);
    if (n == tmp * div_back[q] / meme) {
      printf("%lld", div_back[q]);
      count_k++;
      return 0;
    }
  }
  if (count_k == 0) {
    printf("%d", -1);
  }
  return 0;
}

byeongkeunahn 1년 전 1

5번째 줄에 int를 long long으로 수정해 보시면 좋을 것 같습니다.

jms020820 1년 전 0

조언 감사합니다

5번째 바꿔서 제출했는데 33퍼에서 틀렸네요 ㅠㅠ

다른 문제가 있나봐요

byeongkeunahn 1년 전 1

long long으로 바꿔야 할 게 하나 더 있어요.

반례) 997 998 995005004994

jms020820 1년 전 0

헉!! 루트 n이 int 범위를 넘어설수있었군요 !! 무조건 넘지않을 줄 알고 다른 걸 한참을 봤네요

q를 long long 으로 바꾸고 성공했습니다 감사해요

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

문제

문제

출처

ICPC

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

jms020820 1년 전 0

byeongkeunahn 1년 전 1

jms020820 1년 전 0

byeongkeunahn 1년 전 1

jms020820 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말