[백준] 정수론및조합론 - 2981번 검문 java 자바

문제

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

2981번: 검문

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.
상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.
먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.
N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

풀이

나머지가 같다는 걸 수식으로 생각해보면 다음과 같다.
A1 = M*Q1 + R1
A2 = M*Q2 + R2
라는 식이 있을 때
A1 - A2 = M*Q1 - M*Q2 + (R1-R2)
A1 - A2 = M(Q1 - Q2) (R1 = R2이므로 R1-R2=0)
로 나타낼 수 있다.

즉 M은 A1과 A2의 차의 공약수이다.
이를 구하기 위해서 둘의 최대공약수를 구한 후 이 최대공약수의 약수들을 구하면 된다!

최대공약수를 구하기 위해서 지난 문제들에서 사용했던 유클리드 호제법을 사용하였다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		int N=sc.nextInt();
		int[]arr=new int[N];
		
		for(int i=0;i<N;i++) {
			arr[i]=sc.nextInt();
		}
		
		Arrays.sort(arr);
		
		int num=arr[1]-arr[0];
		
		for(int i=1;i<N;i++) {
			num=gcd(num, arr[i]-arr[i-1]);
		}
		
		for(int i=2;i<=num;i++) {
			if(num%i==0)
				System.out.print(i+" ");
		}
	}
	
	
	public static int gcd(int a, int b) {
		if(b==0) return a;
		else return gcd(b, a%b);
	}

}