#10 정수론 - 나머지의 성질

 나머지에 관한 문제일 경우 모듈러 연산의 성질에 대해 알고있으면 쉽게 해결 가능한 문제들이 많다.

이번에는 모듈러 연산의 성질을 활용하여 문제를 해결해본다.

 

1. 모듈러연산의 덧셈, 뺄셈, 곱셈

(A + B) % C = ((A % C) + (B % C)) % C
(A - B) % C = ((A % C) - (B % C)) % C
(A * B) % C = ((A % C) * (B % C)) % C

 모듈러 연산의 덧셈, 뺄셈, 곱셈에는 분배법칙이 성립한다.  이 성질을 응용하여 수학적으로 해결 가능한 문제도 있으며, 매우 큰 수를 구하는 문제에서 모듈러연산을 취한 값을 반환할 것을 요구할 경우, 단순히 최종값을 구한 뒤 모듈러 연산을 하게되면 자료형의 표현범위에 한계가 있는 언어일 경우 오버플로우가 발생할 수 있으며 Python 처럼 자료형의 표현범위에 제한이 없더라도 메모리 초과 등의 문제가 발생할 수 있기때문에 모듈러 연산의 분배법칙을 이용하여 연산 중간중간에 모듈러 연산을 취해주는 것으로 문제를 해결할 수도 있다.

 

모듈러 연산의 분배법칙을 활용하여 문제(https://www.acmicpc.net/problem/2981)를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.read


def sol2981():
    n, *seq = map(int, input().split())
    g, *diff = [abs(seq[i]-seq[i-1]) for i in range(1, n)]
    for d in diff:
        g = gcd(g, d)
    res = {g}
    for i in range(2, int(g**.5)+1):
        if g % i == 0:
            res.add(i)
            res.add(g//i)
    return ' '.join(map(str, sorted(res)))


def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        a, b = b, a % b
    return a


if __name__ == '__main__':
    print(sol2981())

 모든 수를 나누었을 때 나머지가 같다는 것을 식으로 나타내면 n개의 수를 A1, A2, ... , An 이라 할 때, 

A1 % m = k

A2 % m = k

A3 % m = k

...

와 같은 형태가 된다.

이 때, 인접한 수들끼리 뺄셈을 취하면 Ax % m - A(x-1) % m = 0 과 같은 형태가 된다.  m은 1보다 크기 때문에,

(Ax % m - A(x-1) % m) % m = 0 이 성립한다.  분배법칙에 따라 이는 (Ax - A(x-1)) % m = 0 이 된다. 즉, m은 n개의 수들의 차들의 공약수중 2 이상인 수가 된다.  이를 구하기 위해 인접한 수들의 차를 모두 구한 뒤, 그 차들의 최대공약수를 구한다.  이후 최대공약수의 약수를 모두 구하여 오름차순 정렬한 것이 답이된다.