백준 문제 2981번 검문 문제풀이 c++

https://www.acmicpc.net/problem/2981

2981번: 검문

 

문제해석

 

문제를 보고 처음에 바로 아이디어가 떠오르지않아서 좀 고민을 해보다가 한가지 사실을 발견하였다.

N개의 수를 각각 어떤 수 X로 나눴을때 각각의 나머지가 전부 같으려면 a[0]~a[n-1]를 a[0]~a[n-1]숫자중 가장 작은값을 빼고 a[0]~a[n-1]의 최대 공약수를 구한다. 그 최대 공약수의 약수들이 정답이 된다.(1은 제외)

즉 입력이

6 34 38 이면 여기서 가장 작은 값은 6이므로 6을 빼준 후의 상태는 0 28 32이다.

0 28 32의 최대 공약수는 4이고 4의 약수는 1을제외하고 2 4이므로 답이 2 4이다.

 

5 17 23 14 83이면 가장 작은 값 5를 빼준 후의 상태는 0 12 18 9 78 이다.

0 12 18 9 78의 최대 공약수는 3이고 3의 약수는 1을 제외하고 3이므로 답이 3이다.

 

편의를 위해 오름차 정렬을 한 후 a[0]을 빼준후 최대 공약수는 유클리드 호제법을 사용하여 구했다.

 

코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
priority_queue <int> pq;
int gcd(int n,int m);
int a[100];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    for(int i=n-1; i>=0; i--)
    {
        a[i]=a[i]-a[0];
    }
    int x;
    for(int i=0; i<n-1; i++)
    {
        if(i==0)
        {
            x=gcd(a[i],a[i+1]);
        }
        else
        {
            x=gcd(x,a[i+1]);
        }
    }
    for(int i=2; i*i<=x; i++)
    {
        if(x%i==0)
        {
            if(i==x/i)
            {
                pq.push(-i);
            }
            else
            {
                pq.push(-i);
                pq.push(-(x/i));
            }
        }
    }
    pq.push(-x);
    while(!pq.empty())
    {
        cout<<-pq.top()<<" ";
        pq.pop();
    }
}
int gcd(int n,int m){
    if(n>m)
    {
        int tmp;
        tmp=m;
        m=n;
        n=tmp;
    }
    if(n==0)
    {
        return m;
    }
    else
    {
        return gcd(m%n,n);
    }
}