[ARC148 A] mod M

난이도: 656

 

태그

• Number Theory (정수론)
  • Greatest Common Divisor (최대공약수)

 

풀이

1. 자명하게 생각해볼 수 있는 답의 최댓값은?

만약 \( M = 2 \)를 선택했다면, 모든 원소는 \( 0 \) 또는 \( 1 \)이 될 테니, 이 때의 답은 최대 \( 2 \)가 됩니다.

 

2. 그럼, 답이 \( 1 \)인 경우는?

연산을 1번만 진행할 수 있으니, 모든 \( A_i \text{ mod } M \)이 동일한 \( M \)을 찾아야 합니다.

이를 찾기 위해, 잠시 간단한 경우 \( N = 2 \)를 생각해봅시다.

 

두 수 \( a, b \)에 대해, \( a \text{ mod } M \)과 \( b \text{ mod } M \)가 같은 \( M \)은 뭐가 있을까요?

저게 같다는 건, 어떤 두 수 \( a', b' \)과 나머지 \( m \)에 대해

\( a = a' M + m \)과 \( b = b' M + m \)으로 나타낼 수 있다는 의미가 됩니다.

 

그렇다면, \( a - b = (a' M + m) - (b' M + m) = (a' - b') M \)이 되겠죠.

즉, \( a - b \)는 \( M \)의 배수, 다르게 말하자면 \( M \)은 \( a-b \)의 약수여야 합니다.

 

이제 원 문제로 돌아온 뒤, 위 조건을 적용해보면

\( A_2 - A_1 \)의 약수이면서 \( A_3 - A_2 \)의 약수이면서 ...

가 되므로, \( D_i = A_{i+1} - A_i \)에 대해 \( \text{gcd}(D) \)를 구하면 됩니다.

 

이 값이 \( 2 \) 이상이라면, 그 값을 \( M \)으로 써주면 되고

\( 1 \)이라면, 어떻게 해도 \( 2 \)가지 이상의 수가 나오니 아까 구했던 자명한 최대인 \( 2 \)가 답이 됩니다.

 

코드

ll arr[200020];
 
void Main(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){ cin >> arr[i]; }
    sort(arr+1, arr+n+1);
    ll g = arr[2]-arr[1];
    for (int i = 1; i < n; i++){ g = gcd(g, arr[i+1]-arr[i]); }
    cout << (g==1 ? 2 : 1);
}