BOJ 6030 - Scavenger Hunt

문제

두 양의 정수 P, Q의 약수 쌍을 모두 출력하라. P의 약수와 Q의 약수의 모든 조합을 오름차순으로 출력한다.

입력

두 양의 정수 P와 Q가 주어진다.

출력

P의 약수와 Q의 약수의 모든 쌍을 오름차순으로 출력한다.

예제

입력	출력
`6 12`	`1 1` `1 2` `1 3` `...`

풀이

P와 Q의 약수를 각각 오름차순으로 구한 뒤, 모든 쌍을 이중 반복문으로 출력한다.

sqrt(P)까지 반복하여 P의 약수를 오름차순으로 수집한다
같은 방식으로 Q의 약수를 수집한다
P의 약수와 Q의 약수의 모든 조합을 순서대로 출력한다

핵심 아이디어: 약수를 sqrt(N)까지만 탐색하되, 작은 약수와 큰 약수를 분리 수집 후 합치면 정렬된 약수 목록을 얻을 수 있다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
vector<int> divisors_sorted(int n)
{
  vector<int> lo, hi;
  for (int i = 1; i * i <= n; ++i)
  {
    if (n % i == 0)
    {
      lo.push_back(i);
      if (i * i != n)
        hi.push_back(n / i);
    }
  }
  reverse(hi.begin(), hi.end());
  lo.insert(lo.end(), hi.begin(), hi.end());
  return lo;
}
 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int P, Q;
  if (!(cin >> P >> Q))
    return 0;
 
  auto A = divisors_sorted(P);
  auto B = divisors_sorted(Q);
 
  for (int a : A)
    for (int b : B)
      cout << a << ' ' << b << '\n';
}

복잡도

시간: O(sqrt(P) + sqrt(Q) + d(P) * d(Q)) (d: 약수 개수)
공간: O(d(P) + d(Q))

문제