글 읽기 - 2981 검문

pianojay 4년 전 0

주어진 N개의 숫자에 대해 나누었을 때 나머지가 같도록 하는 수들을 오름차순으로 출력하라는 문제입니다.(1 제외)

N개의 숫자를 배열에 넣은 다음

이웃한 항 끼리의 차(절대값)를 모두 구한 다음에

차들의 최대공약수를 구한 다음

그 최대공약수의 1을 제외한 모든 약수를 출력하도록 했습니다.

시간초과가 일어나네요.

약수를 출력하는 과정에서 문제가 일어난 것일까요? 이보다 더 나은 방법이 생각나지 않네요...

#include <iostream>

int gcd(int a, int b)
{
    int c;
    while(1) {if(b>a) {c=b; b=a; a=c;} if(b==0) {break;} a%=b;}
    return a;
}

int main()
{
    int a; std::cin>>a;
    int *b = new int[a]; for(int i=0;i<a;i++) {std::cin>>b[i];}
    for(int i=0;i<a-1;i++) {b[i]=abs(b[i]-b[i+1]);} b[a-1]=b[a-2];
    for(int i=0;i<a-1;i++) {b[i+1]=gcd(b[i], b[i+1]);}
    int c=b[a-1]; delete [] b;
    for(int i=2;i<=c;i++) {if(!(c%i)) {std::cout<<i<<' ';}}
	return 0;
}

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

문제

문제

출처

ICPC

2981 검문 - 시간 초과

pianojay 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말