백준13412 - 서로소 쌍

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

13412번: 서로소 쌍

생각보다 너무 어렵게 풀었다. 간단한 풀이는 N의 약수를 구하는 데 루트를 이용하여 제수가 될 수 있는 범위를 줄인 후 약수를 구한 다음 sort함수로 정렬한 후 유클리드 호제법으로 최대공약수를 구했을 때 1이 나오면 된다. 하지만 나는 정렬을 사용하지 않고 무식하게 조합을 이용하여 모든 약수를 2개씩 뽑아서 곱하였을 때 N이 되지 않으면 거르고 이 뽑은 두 수의 최대공약수가 1이 아니면 거르는 방식을 사용하였다. 다음부터는 조금 더 고민하고 짜야겠다.

 

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

int T, N, cnt = 0; //T는 테스트 케이스, N은 원하는 수, cnt는 경우의 수
vector<int> v; //v는 약수들의 집합
vector<bool> visit; //visit은 방문 여부
vector<int> check; //check는 뽑은 수의 정보

//유클리드 호제법을 이용한 최대 공약수 구하기
int GCD(int x, int y) {
	if (y == 0) {
		return x;
	}
	return GCD(y, x % y);
}

//조합 구현, dfs개념이 들어감, 방문여부로 순서에 상관없이 원하는 갯수를 뽑는다. 원래 뽑은 갯수가 맞으면 다시 그 수를 삭제하고 다음에 뽑을 수를 찾는다.
void Com(int start, int depth) {
	if (depth == 2) {
		if (check[0] * check[1] != N) {
			return;
		}
		if (GCD(check[0], check[1]) == 1) {
			/*cout << check[0] << ' ' << check[1] << '\n';*/
			cnt++;
		}
		return;
	}
	for (int i = start; i < v.size(); i++) {
		if (visit[i]) {
			continue;
		}
		check.push_back(v[i]);
		visit[i] = true;
		Com(i, depth + 1);
		check.pop_back();
		visit[i] = false;
	}
}


int main() {
	cin >> T;
	while (T--) {
		cin >> N;
		if (N == 1) { //1과 1은 서로소인 것을 가까먹지 말아야한다.
			v.push_back(1);
			v.push_back(1);
			visit.push_back(false);
			visit.push_back(false);
		}
		else {
			//루트를 이용한 약수 찾기, 시간 단축에 효율적이다.
			for (int i = 1; i * i < N; i++) {
				if (N % i == 0) {
					v.push_back(i);
					v.push_back(N / i);
					visit.push_back(false);
					visit.push_back(false);
				}
			}
			if (sqrt(N) == int(sqrt(N))) { //제곱 수인 경우 약수를 하나만 지정하기 위하여 설정, sqrt함수가 반환형이 실수형으로 정수형과 비교하였을 때 오차가 없으면 제곱수이다.
				v.push_back(int(sqrt(N)));
				visit.push_back(false);
			}
		}
		Com(0, 0); //조합 수행
		cout << cnt << '\n';

		//모든 공간 초기화, 경우의 수 결과 초기화
		v.clear();
		visit.clear();
		check.clear();
		cnt = 0;
	}
}