BOJ 2981: 검문

작성일

https://www.acmicpc.net/problem/2981

  • 2월동안 187문제 풀기(지난달 누적 87개) (38/187)
  • 너무 쉬웠던 패션왕 신해빈은 생략
  • 요거는 아주 새로웠음.
  • 솔직히 책정된 난이도보다 나한테는 훨씬 어려웠음
  • gcd 구하고 이런건 알겠는데, 나눠서 나머지가 같은 수를 찾는 방법 자체가 어려웠음
    • 수들의 차를 구해서 그 차의 gcd를 구하면 되는거였음
    • $V_b-V_a=(xQ_b+r) - (xQ_a + r) = x(Q_b - Q_a)$
    • 나머지가 같다면 위와 같은 식이 되는데, 뺀 수를 기준으로는 $V_{diff} = xQ_{diff}$ 와 같은 식이 됨.
    • 모든 차에 대해서 가장 커질수 있는 공통된 x를 찾는다면, 그건 gcd임.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> arr, comb;
int gcd(int a, int b) {
  return b != 0 ? gcd(b, a%b) : a;
}

int main() {
  cin >> N;
  arr.resize(N);
  for(int i =0; i < N; i++)
    cin >> arr[i];
  sort(arr.begin(), arr.end());
  for(int i =0; i < N; i++)
    for(int j =i+1; j < N; j++)
      comb.push_back(arr[j]-arr[i]);

  int g = comb[0];
  for(int j = 1; j < comb.size(); j++)
    g = gcd(g, comb[j]);

  set<int> ans;
  ans.insert(g);
  for(int i = 2; i*i <= g; i++)
    if (g%i == 0)
      ans.insert(i), ans.insert(g/i);
  for(int i : ans)
    printf("%d ", i);
}