검문 풀이

문제 링크: https://www.acmicpc.net/problem/2981

백준 정수론 및 조합론 5단계 - 2981번 검문을 풀어보았다.

 

풀이: 수를 서로 뺀 후 최대공약수를 찾고, 최대공약수의 약수를 찾으면 된다.

 

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>

using namespace std;

int main()
{
	int n;
	cin>>n;
	vector<int>v(n);
	for(int i=0;i<n;i++) cin>>v[i];
	sort(v.begin(),v.end());
	vector<int>v1;
	for(int i=1;i<n;i++) v1.push_back(v[i]-v[i-1]);
	int tmp=v1[0];
	for(int i=1;i<n-1;i++) tmp=gcd(tmp,v1[i]);
	vector<int>res;
	for(int i=2;i<pow(tmp,0.5)+1;i++)
	{
		if(tmp%i==0)
		{
			res.push_back(i);
			res.push_back(tmp/i);
		}
	}
	res.push_back(tmp);
	sort(res.begin(),res.end());
	res.erase(unique(res.begin(),res.end()),res.end());
	for(auto i:res) cout<<i<<' ';
}

Python

import math

n=int(input())
arr=[]
for i in range(n):
	arr.append(int(input()))
arr.sort()
narr=[]
for i in range(1,n):
	narr.append(arr[i]-arr[i-1]) # 차를 입력
temp=narr[0]
for i in range(1,n-1):
	temp=math.gcd(temp,narr[i]) # 최대공약수 찾기
result=[]
for i in range(2,int(temp**0.5)+1): # 시간절약을 위해 제곱근까지만
	if temp%i==0:
		result.append(i)
		result.append(temp//i)
result.append(temp) # 최대공약수의 약수 찾기
result=list(set(result)) # 중복제거
result.sort()
for i in result:
	print(i, end=' ')

Java