글 읽기 - 한 11%에서 오답이 뜨는데 원인이 뭘까요?

furyhunter 7년 전 0

입력받은 A와 B를 이루는 숫자들끼리 각각 최대공약수를 구해서 그걸 다 곱하는 방향으로 코드를 짜봤습니다

이것저것 테스트 해봤는데 잘 돌아가서 제출해봤는데

케이스 4개정도 돌아가고 오답이 뜨네요..

혹시 제가 놓친 부분이나 오류가 나는 케이스가 있을까요?

아니면 혹시 출력 문제일까요..?

#include <iostream>

using namespace std;

long long gcd(long long A, long long B)
{
	while (B != 0)
	{
		long long temp = A % B;
		A = B;
		B = temp;
	}

	return A;
}

int main()
{
	int N, M;
	long long arrN[1001] = { 0 }, arrM[1001] = { 0 };
	long long answer = 1;

	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> arrN[i];

	cin >> M;

	for (int i = 0; i < M; i++)
		cin >> arrM[i];

	int i = 0;

	while (i < N)
	{
		if (arrN[i] == 1)
		{
			i++;
			continue;
		}

		for (int j = 0; j < M; j++)
		{
			long long x = gcd(arrN[i], arrM[j]);

			if (x == 1)
				continue;
			else
			{
				answer *= x;
				arrN[i] /= x;
				arrM[j] /= x;
			}
		}

		i++;
	}

	if (answer >= 1000000000)
		printf("%09lld\n", answer % 1000000000);
	else
		cout << answer << "\n";

	return 0;
}

jseo 7년 전 0

오버플로우 날 것 같네요.

1000000000 1000000000 1000000000

furyhunter 7년 전 0

음.. 문제에서 모든 입력이 1000000000보다 작다고 합니다..

jseo 7년 전 0

제가 말하고 싶었던건 A와 B의 최대 공약수가 64비트 정수형을 초과할때 오버플로우가 생길것 같다는 겁니다.

999999999 999999999 999999999

를 넣어도 오버플로우가 나는건 다르지 않을겁니다.

furyhunter 7년 전 0

답변 감사합니다!

51번째 줄을 answer = (answer * x) % 1000000000; 로 고쳐서 오버플로우 문제는 해결한 것 같습니다

그런데 제출해보니 이번엔 아예 처음부터 틀렸다고 나오네요..

문제가 뭘까요 ㅠㅠ

jseo 7년 전 0

실제 답이 예를 들어서 1000000001일때 출력은 000000001이 되어야 하지만 단순히 나머지만 구하면 그냥 1을 출력할겁니다.

나머지를 구하는 과정에서 곱한 결과값이 한번이라도 1000000000 이상이었는지 체크할 필요가 있습니다.

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

문제

문제

출처

ICPC

한 11%에서 오답이 뜨는데 원인이 뭘까요?

furyhunter 7년 전 0

jseo 7년 전 0

furyhunter 7년 전 0

jseo 7년 전 0

furyhunter 7년 전 0

jseo 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말