태그:
주어진 N개의 수를 나누었을 때 나머지가 같게 되는 제수를 모두 구하는 문제입니다. 이 문제는 나머지 연산의 성질을 이용하여 알고리즘을 최대한 간단히 만들어 푸는 문제입니다. 주어진 수열을 a라고 하면, 먼저 가정에 의해 \(a_i=k_iM+r(0\le r\lt M)\)로 나타낼 수 있어야 하고, 임의의 두 원소의 차이는 M의 배수가 되야 합니다. 이를 만족하는 M의 성질을 알아보겠습니다.
\[a_i=k_iM+r(0\le i\lt N,0\le r\lt M,k_i\in \mathbb{N})\\ \text{Let }b_i=a_{i+1}-a_i=(k_{i+1}-k_i)M\equiv 0\pmod{M}\\ \Rightarrow M|b_i(0\le i\lt N-1)\\ \therefore M|\text{gcd}\{b_i\}(0\le i\lt N-1)\]우선 M은 a의 인접한 두 원소의 차의 공약수인 것을 알아냈습니다. 그런데, a의 인접한 두 원소의 차이의 공약수는 a의 임의의 두 원소의 차이의 공약수와 같습니다. 그 이유는 아래와 같습니다.
\[\begin{align*}a_k-a_j&=(a_k-a_{k-1})+(a_{k-1}-a_{k-2})+...+(a_{j+1}-a_j)\\ &=b_{k-1}+b_{k-2}+...+b_j\\ &\equiv 0+0+...+0\pmod{M}\\ &\equiv 0\pmod{M}\end{align*}\]즉, 임의의 두 원소의 차이 또한 M으로 나누어 떨어집니다. 따라서 이 문제를 풀 때 인접한 두 원소의 차이만을 가지고 조건을 만족하는 M을 찾을 수 있습니다. 문제를 풀 때에는 우선 배열(순서가 바뀌어있는 상태여도 상관이 없습니다) 인접한 두 원소의 차이를 모두 구해놓고, 이들의 최대공약수를 구한 뒤 그 약수 중 1을 제외한 약수를 모두 출력하면 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-04-02 11:29:29 |