글 읽기 - 1037번 약수...간단합니다 봐주세요 ㅠ

gkfkagkfka12 5년 전 0

먼저 최소공배수를 쭉 구하면서 가장 큰 값을 찾습니다.

다 계산한 후에 최소공배수가 가장 큰 값이랑 같을 경우 A=N인 경우이므로 *2를 해주어 출력하고 아니면 그냥 출력합니다.

질문란에 있는 모든 예제 다 돌려보고 맞는데 안되네요ㅠㅠ 숫자범위가 큰 경우 예시에는 답이 없어서 답을 모르겠네요

#include <cstdio>

long long y[50];

long long gcd(long long a, long long b)
{
	// gcd(a,b) = gcd(b,r)
	while (b) {
		long long r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main(void)
{
	long long n; scanf("%lld", &n);
	long long ans = 1, max = 0;

	for (long long i = 0; i < n; i++) {
		scanf("%lld", &y[i]);
		if (max < y[i]) max = y[i];
		ans = (ans*y[i]) / gcd(ans, y[i]);
	}

	ans == max ? printf("%lld", ans * 2) : printf("%lld", ans);
	return 0;
}

jh05013 5년 전 0

아니요, 바로 세 번째 글에 반례가 있습니다.

gkfkagkfka12 5년 전 0

1

3

이면

6이 답 아닌가요??

jh05013 5년 전 1

"어떤 수 N의 진짜 약수가 모두 주어질 때"

답이 6이려면 2도 주어져야 합니다. 답은 9입니다.

gkfkagkfka12 5년 전 0

이제 틀린걸 알아서 2가지 경우로 나눴습니다.

- 약수가 1개인 경우 : 약수가 1개이므로 해당 숫자는 반드시 소수여야 합니다 따라서 제곱한 값이 답입니다.

- 약수가 2개 이상인 경우 : 최소공배수가 답이어야 하는데 가장 큰 숫자와 최소공배수가 같을 경우 A=N이므로 최소공배수에 2를 곱한 값이 답입니다.

어떤 부분이 틀렸나요?

jh05013 5년 전 1

N이 최소공배수 * 2면 2를 약수로 가집니다. 하지만 입력에 2가 없을 수도 있습니다.

gkfkagkfka12 5년 전 0

그러면 최소공배수 == 가장 큰 숫자인 경우가 없으니까 그냥 최소공배수를 출력해주면 되는 거 아닌가요...? 틀리네요...

jh05013 5년 전 2

그런 경우는 얼마든지 있습니다.

2

3 9

답은 27입니다.

하나 힌트를 드리자면, 루트N을 제외한 모든 약수는 둘씩 짝지어서 짝지은 두 수의 곱이 N이 되도록 할 수 있습니다.

gkfkagkfka12 5년 전 0

정렬해서 최솟값*최댓값 하니까 맞네요... 감사합니다. 그런데 원리가 정확히 이해가 안됩니다.

왜 약수의 최댓값*최솟값이 원래 수가 되나요? 어렴풋이는 알겠는데 엄밀한 증명을 못하겠네요.

jh05013 5년 전 1

d가 작을 수록 N/d가 큽니다. 그러므로 가장 작은 약수와 가장 큰 약수를 짝지을 수 있습니다. 그런데 그건 사실 1과 N이라서 입력으로 주어지지 않고, 두 번째로 작은 약수와 두 번째로 큰 약수를 짝지으면 답을 알 수 있습니다.

gkfkagkfka12 5년 전 0

음... 그러니까 가장 작은 약수 d가 있다고 했을 때 결국 N/d는 가장 큰 약수가 되는데 (N/d)*d = N이니까 증명이 된다고 보면 될까요?

jh05013 5년 전 1

그렇습니다.

gkfkagkfka12 5년 전 0

꾸준한 답변 감사드립니다!

krenerd 5년 전 0

3

2 3 5

라고 입력하면 30이 나와야 하지 않나요?

krenerd 5년 전 0

최대(5)* 최소(2)를 하면 10이 출력되는데 문제이해를 잘못한 것일까요?

jh05013 5년 전 0

2 3 5는 아예 잘못된 입력입니다. N의 진짜 약수가 전부 주어진다고 되어 있습니다.

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