[백준 2981] 검문

[ 백준 2981 : 검문 ]


일단 N개의 자연수가 1보다 큰 M 으로 나눴을때 나머지가 모두 같아야한다.
N개의 자연수 배열을 A[i=1~100] 이라고 예를 들어보자.

A[1]이라는 수를 1보다 큰 어떤 M이라는 숫자로 나눠보자
몫은 A[1]/M 이되고 나머지는 A[1]%M 이 된다.

한개의 식으로 바꿔보면 A[1] = A[1]/M * M + A[1]%M 이런식으로 구성된다.
이때 A[1]%M ~ A[N]%M 이 모두 같아야한다.
몫은 상관이 없다.

다시 수식으로 바꿔보면

A[1] = A[1]/M * M + A[1]%M
A[2] = A[2]/M * M + A[2]%M
.
.
.
A[N] = A[N]/M * M + A[N]%M

이제 나머지로 한 번 풀어본다.
그럼

A[1]%M = A[1] - A[1]/M * M = A[2]%M = A[2] - A[2]/M * M 이 된다.

=> 나머지 = A[1] - A[1]/M * M = A[2] - A[2]/M * M 라는 식이 성립한다.

한쪽으로 넘겨 0으로 만들어보자.
=> A[1] - A[2] - A[1]/M * M + A[2]/M * M = 0

=> A[1] - A[2] - M * (A[1]/M - A[2]/M) = 0

=> A[1] - A[2] = A[1]/M * M - A[2]/M * M

=> A[1] - A[2] = M * (A[1]/M - A[2]/M)

이제부터 몫을 B1,B2,B3...BN이라고 정의해보자.

A[1] - A[2] = M * (B1 - B2)
A[2] - A[3] = M * (B2 - B3)
A[3] - A[4] = M * (B3 - B4)
A[4] - A[5] = M * (B4 - B5)
...
..
A[N-1] - A[N] = M * (BN-1 - BN)

N-1과 N의 차는 M이라는 공통된 약수를 갖는다.

지금 이 공식들은 뭘 설명하는 걸까?

바로 모두 같은!!!! 나머지를 가질때는 어떤 수에서 다른 어떤 수를 뺄때 M이라는 공통된 약수를 가진다는 것이다.

그럼 이제 M은 어떻게 구할까?

바로바로바로 공약수중에 가장 큰 공약수 최대 공약수를 구하면 된다.

최대 공약수는 유클리드 호제법으로 간단하게 재귀함수로 처리해버린다.

RECUR(int a,int b) {
if(b==0 ) return a;
else return RECUR(b,a%b);}

로 간단히 구할 수 있다.

나는 n이 100이므로 그냥 처음에 정렬한 상태에서 시작을 했당.
A1이 가장 큰 수이고 AN이 가장 작은 수이다.

그리고 M인 최대공약수를 구하고 이제 M의 약수를 뽑는다.

약수를 뽑을땐 1부터 M의 제곱근만큼만 보면서 나누어떨어지는지 계산하면된다.

만약 M이 9억이면 9억까지 봐야하므로 곤란하다.
이를 9^0.5 까지만 본다면 30000번만 보면 된다.


제곱근까지만 보는 이유는 제곱근 이후의 수는 계산으로 가능하기때문이다.