2981 : GRANICA

네르기·2021년 8월 27일

알고리즘

목록 보기

27/76

어떤 문제인가?

$M$ 과 여러 수가 주어졌을 때, 각 수를 $M$ 으로 나눈 나머지가 같게 하는 $M$ 을 찾는 문제. 그러니까,

\forall a, b \in \mathbb{N}, a \equiv b (mod\,M), M > 1

을 만족시키는 $M$ 을 찾는 문제.

문제의 조건

우선 $M$ 이 1개 이상 존재할 조건은 다음과 같다.

\gcd(X_{1},X_{2},X_{3},\dots,X_{n-1}) > 1, X_{n} = |a_{n+1}-a_{n}|

그러니까, 주어진 모든 수의 최대공약수가 1보다 커야 한다.

모듈러 연산 분해

나눗셈은 다음과 같이 대수적으로 표현할 수 있다.

A = M\times q + r

그리고 이걸 $mod\,M$ 으로 표현하면 다음처럼 된다.

A\mod\,M = r

내가 부딪힌 부분 (1)

처음에는 나머지를 0부터 주어진 수 중 가장 작은 수까지 늘려가면서 $M$ 을 찾아보려고 했다. 그러나 그 방법은 이 경우에 대해 시간 초과가 난다.

10^9-1, 10^9

앞서 말한 대수적 표현을 떠올렸더니 나머지를 제거하면 되겠다는 생각이 들었다. 어차피 주어지는 모든 수들은 나머지가 전부 같지 않던가? 모든 수들을 각자 빼버리자. 예를 들어 이런 수들이 주어졌다면,

5, 17, 23, 14, 83

이 수들의 차를 다 구해보자. 물론 절댓값이어야 한다. 경우의 수는 $\frac{n(n-1)}{2}$ 다. 수들의 순서는 상관 없다. 5에서 17을 빼던, 5에서 83을 빼던 상관이 없다.

12, 18, 9, 78, 6, 3, 66, 60, 69

이 수들의 최대공약수를 찾아야 한다. 유클리드 호제법으로 구한다.

두 개 이상의 수가 주어졌을 때 최대공약수를 구하려면, 어떤 두 수의 최대공약수를 먼저 구하고, 그 최대공약수와 나머지 수의 최대공약수를 구하면 된다.

오잉? 그냥 최솟값만 구하면 되지 않나요?

혹시나 위 예제를 보고 그런 생각이 들었다면, 다음과 같은 반례에 의해 틀린다.

1, 5, 11, 19

최솟값만 구한다면 4겠지만, 최대공약수는 2다.

내가 부딪힌 부분 (2)

최대공약수까진 다 구했는데, 약수를 보여줄 방법이 떠오르지 않는다. 2부터 최대공약수까지 한번씩 검사하는 방법은 최대 검사 수가 $10^9$ 에 달하기 때문에 무조건 시간 초과가 난다.

그렇다고 인수분해를 해서 이들 인수를 모두 곱한 경우를 일일히 BFS로 보여주는건 정신이 나갈 짓인것 같다. 더 간단한 방법이 없을까?

1, 2, 4, 8, 16, 32

$1 \times 32 = 32$
$2 \times 16 = 32$
$4 \times 8 = 32$

아하! 짝끼리 곱하면 원래 수가 되니 이를 이용해야겠구나!
이 방법을 사용하면 위의 $O(n)$ 방식보다 더 빠른 $O(\sqrt{N})$ 방식으로 구현할 수 있다.

최종본

#include <stdio.h>
#include <stdlib.h>

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

int main() {
    int N,i,j,t,*X,m;
    scanf("%d",&N);
    X = (int*)calloc(4,N);
    for(i=0;i<N;i++)
        scanf("%d",&X[i]);
    m=abs(X[1]-X[0]);
    for(i=1;i<N;i++) {
        for(j=0;j<i;j++) {
            t = abs(X[i]-X[j]);
            if(g(t,m)<m) m=g(t,m);
        }
    }
    for(i=2;i*i<m;i++) {
        if(m%i==0) printf("%d ", i);
    }
    if(i*i!=m) i--;
    for(j=i;j>0;j--) {
        if(m%j==0 && m/j>1) printf("%d ",m/j);
    }
}