[백준 17436] 소수의 배수

문제

www.acmicpc.net/problem/17436

17436번: 소수의 배수

 

문제 풀이

 

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;
}