글 읽기 - (C++) 어떤 부분 때문에 틀리는 걸까요

tmdwp54977 1년 전 0

정렬 후 diff 배열을 계산해서 diff[] 내의 값이 음수인 경우 X

input : 2 2 4에 대해 gcd가 2인데, for(i = 2;i <= sqrt(gcd);i++)과 같이 범위를 잡으면 2를 못 찾는 문제 X

gcd가 제곱수여서 gcd % i == i일 때 중복된 값이 들어가는 경우 X

divisor 배열을 정렬 후 1번 index부터 출력해서 1은 출력하지 않음

등 질문 게시판에 나오는 거의 대부분의 반례를 처리한 듯 한데 어떤 부분에서 문제가 생기는 지 모르겠습니다.

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n, i, gcd, mod, cnt = 0, arr[100], diff[99], divisor[1000];

    scanf("%d", &n);
    for(i = 0;i < n;i++)
        scanf("%d", &arr[i]);
    sort(arr, arr + n);

    for(i = 0;i < n - 1;i++)
        diff[i] = arr[i + 1] - arr[i];

    gcd = diff[0];
    for(i = 1;i < n - 1;i++) {
        while(mod != 0) {
            mod = gcd % diff[i];
            gcd = diff[i];
            diff[i] = mod;
        }
    }

    for(i = 1;i <= (int)sqrt(gcd);i++) {
        if(gcd % i == 0) {
            divisor[cnt++] = i;
            if(i * i != gcd)
                divisor[cnt++] = gcd / i;
        }
    }

    sort(divisor, divisor + cnt);

    for(i = 1;i < cnt;i++)
        printf("%d ", divisor[i]);

    return 0;
}

zenith82114 1년 전 1

반례입니다.

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

문제

문제

출처

ICPC

(C++) 어떤 부분 때문에 틀리는 걸까요

tmdwp54977 1년 전 0

zenith82114 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말