BOJ 2981번 :: 검문

#문제

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

2981번: 검문

 

#작성 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
 
int n;
int num[100];
vector<int> prime;
 
int gcd(int a, int b){
    return a%b?gcd(b, a%b):b;
}
 
int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>num[i];
    }
    sort(num, num+n);
    int Gcd = num[1]-num[0];    
    for(int i=2; i<n; i++){
        Gcd = gcd(Gcd, num[i]-num[i-1]);
    }
 
    // 최대공약수의 약수 찾기!!
    // 약수를 찾으면 하나씩 prime 벡터에 넣는다. 
    for(int i=1; i*i<=Gcd; i++){
        if( Gcd%i==0 ){
            prime.push_back(i);
            if( i==1 ) prime.pop_back();
            if(Gcd/i==i) continue;
            prime.push_back(Gcd/i);
        }
    }
    sort(prime.begin(), prime.end());
    for(int i=0; i<prime.size(); i++){
        cout<<prime[i]<<' ';
    }
    return 0;
}

##

입력받은 숫자를 a0, a1, ... an-1이라고 하면 m이 하나 이상 존재하는 입력이 들어오므로

a0 = m*b0 + d

a1 = m*b1 + d

...

an-1 = m*bn-1 + d

의 꼴이 된다.

따라서 an-1 - an-2 = m(bn-1 - bn-2), ... , a1-a0 = m(b1-b0) 이 되므로

i=1 ~ n-1에서 ai-ai-1들의 최대공약수를 구하면 모든 ai에 대해 m*bi를 나눠떨어지도록 하는 수가 된다.

그 최대 공약수를 k라고 하면, k의 약수들도 m*bi를 나눠떨어지게 할 수 있다.

=> k를 구하고, k의 약수들을 오름차순으로 출력하면 되는 문제.