[C++] GLCCDM (백준 32649번)

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

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int a, b, k;
    cin >> a >> b >> k;

    vector<int> ans;
    ans.push_back(a);
    ans.push_back(b);

    for (int i = a + 1; i < b; i++) {
        if (i % a == 0 && b % i == 0) ans.push_back(i);
    }

    if (ans.size() >= k) {
        for (int i = 0; i < k; i++) cout << ans[i] << ' ';
        cout << '\n';
    } else {
        cout << "-1\n";
    }
}

캐어려운 정수론 문제인줄 알았는데 그냥 브루트포스 문제였다 ㅎㅎ;;

핵심 포인트는 d는 A의 배수이면서 B의 약수여야 한다는 것이다. 그런데 A와 B의 범위가 그렇게 크지 않으니 그냥 A부터 B까지의 모든 수를 탐색하면서 체크해서 ans 배열에 추가해주면 된다. (참고로, A와 B는 당연히 정답에 포함되는 수이다.) 마지막에 ans 배열의 크기가 k보다 작으면 -1을 출력하고, k보다 크거나 같으면 ans 중에 아무 수 k개를 출력해주면 된다. (AC)

 

친오빠 붙잡고 뻘짓한 흔적... 그래도 의미 있는 시간이었다. 

식을 좀 정리해보면 다음과 같다.

 

그래서~~ 만약 A와 B의 범위가 큰 문제였다면 이런식으로 판별해야 하지 않을까~