글 읽기 - 어디서 틀렸는지 도저히 모르겠어요...

heartofdreamer 6년 전 0

인접해 있는 항들끼리의 차이를 구해서 그들의 gcd를 구해 그 gcd의 1을 제외한 약수를 구하면 되는거지 않나요?

인접해 있는 항들끼리만 한 이유는 a[j] - a[i]=a[j] - a[j-1] + ... + a[i+1] - a[i]이라서 항상 a[i+1]-a[i]보다 크고 그 공약수들로도 나누어지기때문에 그렇게 했어요.

시간초과면 약수 구하는 부분에서 수정 할텐데 그게 아니라 그냥 틀렸습니다. 라고 해서 어디가 틀렸는지 도저히 모르겠어요.

#include <cstdio>
#include <queue>
using namespace std;

int gcd(int a, int b)
{
	return (a%b == 0) ? b : gcd(b, a%b);
}
int main()
{
	int n;
	priority_queue<int> q;
	scanf("%d", &n);
	int pre, next;
	scanf("%d", &pre);
	for (int i = 0; i < n - 1; i++)
	{
		scanf("%d", &next);
		q.push(pre - next);
		pre = next;
	}
	int c = q.top();
	q.pop();
	int r = (-1)*c;
	while (!q.empty())
	{
		r = gcd(r, (-1)*q.top());
		q.pop();
	}
	for (int i = 2; i <= r; i++)
	{
		if (r%i == 0)
			printf("%d ", i);
	}
	return 0;
}

chogahui05 6년 전 0

하나 궁금한 게 있는데요.

오름차순으로 주어진다고 한 경우에만 동작하는 코드인거 같은데요.

입력이 오름차순으로 주어진다는 조건이 어디에 있나요?

chogahui05 6년 전 0

한 가지 더 주자면.

이 코드는 요런 입력에 대해서 시간 초과가 날 거 같습니다.

12의 약수를 구한다고 해 봅시다.

12까지 나눠봐야 12의 약수를 모두 구할 수 있을까요?

heartofdreamer 6년 전 0

출력을 오름차순으로 쓰라고 한걸 입력이 오름차순이다라고 잘못 이해하고 풀었네요 바꾸니까 바로 되네요! 감사합니다!

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

문제

문제

출처

ICPC

어디서 틀렸는지 도저히 모르겠어요...

heartofdreamer 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 0

heartofdreamer 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말