티스토리 뷰

문제

www.acmicpc.net/problem/17436

 

17436번: 소수의 배수

첫째 줄에 N(1 ≤ N ≤ 10)과 M(1 ≤ M ≤ 1012)이 주어진다. 둘째 줄에는 N개의 소수가 주어진다. 입력으로 주어지는 소수는 100보다 작거나 같으며, 같은 소수가 두 번 이상 주어지지 않는다.

www.acmicpc.net

 

문제 풀이

 

m의 범위를 못보고 계속 int형으로 제출해 삽푼문제였다.


1. 우선 m에 대해 각각의 소수로 나눴을 때 나누어 떨어지는 개수를 모두 세어보면 m/p[0] , m/p[1] ...등이 있을 것이다.

 

2. 이 때 간단한 예시를 통해 생각해보면 중복으로 카운트되는 수들이 존재하는 걸 알 수 있다.

  • m = 30, p[0]= 2 ,p[1] = 3 일 때, p[0]에선 2,4,6...30 p[1]에선 3,6,9...30 // 6의 배수가 중복으로 카운트

3. 백트래킹으로 가능한 소수의 조합을 모두 구한뒤, 포함배제원리를 사용해 개수를 관리해준다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int n;
long long m, ans, gop;
vector<int> p, picked;

void go(int st, int topick) {
	if (topick == 0) {
		gop = 1;
		for (int i : picked) gop *= p[i];
		if (picked.size() % 2) ans += m / gop;
		else ans -= m / gop;
		return;
	}
	for (int i = st + 1; i < n; i++) {
		picked.push_back(i);
		go(i, topick - 1);
		picked.pop_back();
	}
}

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

	cin >> n >> m;
	p.resize(n);
	for (int i = 0; i < n; i++)
		cin >> p[i];
	for (int i = 1; i <= n; i++)
		go(-1, i);
	cout << ans;
}

 

'Algorithm > BOJ' 카테고리의 다른 글

[백준 3673] 나눌 수 있는 부분 수열  (0) 2020.09.08
[백준 1655] 가운데를 말해요  (0) 2020.09.06
[백준 16402] 제국  (0) 2020.09.05
[백준 19576] 약수  (0) 2020.08.31
[백준 19588] 상품권 준비  (0) 2020.08.31
댓글