글 읽기 - 예외케이스를 못찾겠습니다.

allgoodlife 7년 전 0

안녕하세요. 프로그래밍 공부하는 대학생입니다. 2436번 공약수 문제를 풀었는데, 예외케이스를 잘 못찾겠습니다.

로직상 무엇 잘못 되었는 지도 모르겠구요.. 다른분들 질문을 보아도 잘 모르겠네요~ 혹시 찾아주시면 정말 감사하겠습니다:)

#include <iostream>
using namespace std;

int main(void) {
	long gcd=1, lcm=1;
	long a = 0, b = 0;
	long ab = 0;
	long tmp = 0;
	long sum = 100000000;
	long c = 0, d = 0;
	cin >> gcd >> lcm;
	//exception  - lcm or gcd is 0
	if(lcm == 0 || gcd == 0)
		cout << gcd << " " << gcd << endl;
	//normal case
	else if (lcm%gcd == 0)
	{
		//when it is form of a^2
		if (lcm == gcd) {
			cout << gcd << " " << gcd << endl;
		}
		//when it is not a a^2 form
		else {
			ab = lcm / gcd;
			for (int i = 1; i*i < ab; i++)
			{
				if (ab%i == 0) {
					c = i;
					d = ab / i;
					if ((c + d) < sum) {
						sum = c + d;
						a = c;
						b = d;
					}
				}
				if (a > b) {
					tmp = a;
					a = b;
					b = tmp;
					break;
				}
			}
			cout << a*gcd << " " << b*gcd;
		}
		
	}
	else
	{
		cout << gcd << " "<<lcm;
	} 
	


	return 0;
}

zych1751 7년 전 1

lcm = gcd * a * b라고 했을때, a, b는 서로소라는 조건이 필요합니다.

4 64

의 경우,

4 64가 나와야 하는데 위 코드는

8 32가 나오고 있습니다.

allgoodlife 7년 전 0

말씀하신대로 서로소인 부분을 추가했습니다. 그런데도 오류가나는데,

두개의 수를 입력받고 조건을 만족하는 두 수가 존재하지 않을 때 아무것도 출력하지 않게 했는데

이건 상관없나요?? 문제에서 명시적으로 이야기해주지 않아서 잘 모르겠습니다.

#include <iostream>
using namespace std;

int main(void) {
	long gcd = 1, lcm = 1;
	long A, B;
	long ab;
	long a = 0, b = 0;
	long sum = 100000000;
	long AB = 0;
	long tmp1, tmp2;
	long tmp;
	cin >> gcd >> lcm;
	if (lcm%gcd != 0)
		return 0;
	else {
		if (lcm == gcd) {
			A = lcm;
			B = A;
		}
		else
		{
			ab = lcm / gcd;
			a = 1;
			b = ab;
			for (int i = 2; i*i <= ab; i++)
			{
				if (ab % i == 0) {
					tmp1 = i;
					tmp2 = ab / i;
					//서로소 체크
					if (tmp2%tmp1 == 0)
						continue;
					else {
						if (tmp1 + tmp2 < sum) {
							sum = tmp1 + tmp2;
							a = tmp1;
							b = tmp2;
						}
					}

				}

			}
			if (a > b) {
				tmp = a;
				a = b;
				b = tmp;
			}
			A = gcd * a;
			B = gcd * b;
		}
		cout << A << " " << B;
	}



	return 0;
}

zych1751 7년 전 2

불가능한경우는 처리하지 않으셔도 상관없습니다.

지금 서로소 체크가 잘못되고 있는데,

14 21의 경우 서로소가 아니지만(7로 나누어 떨어지므로), 21%14 = 7 이므로 위와 같은 방법으로는 확인할 수 없습니다.

a, b가 서로소일 조건은 a와 b의 최대공약수가 1인 경우로 확인하시면 됩니다.

allgoodlife 7년 전 0

감사합니다. 코딩실력이 많이 부족한데 덕분에 하나 배웠네요^^ 알려주신것 참고하여 다시 해보겠습니다.

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

문제

문제

출처

ICPC

예외케이스를 못찾겠습니다.

allgoodlife 7년 전 0

zych1751 7년 전 1

allgoodlife 7년 전 0

zych1751 7년 전 2

allgoodlife 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말