윤호는 M개의 N보다 작은 숫자가 적혀져있는 마법약들을 가지고 있다.
마법약은 1을 제외한 약수들중 하나로 추출 할 수 있다.
추출에 성공하려면 추출한 제품들 중에서 어떠한 원료도 공유해서는 안된다.
윤호의 추출할 수 있는 최대 마법약의 개수를 구하는 문제이다.
마법약들을 추출했을 때 모든 마법약들의 원료들이 서로소인 최대 마법약 개수를 구하는 것이다.
gcd를 이용하기에는 구할 방법이 마땅히 없어보였다.
사실상 원료들이 서로소가 되려면 마법약에서 추출할 수 원료들을 소수로 추출하면 된다.
문제는 최대 마법약 개수를 구해야하는데 이분매칭을 이용하면 된다.
N이 100,000,000이므로 최대 10,000까지의 소수만 구해주면 되는데 여기 실수가 있었다.
10,000보다 큰 수가 들어올 때 10,000보다 작은 소수로 소인수 분해를 하더라도 끝나지 않을 수 있다.
예를들어 104,729와 같은 수이다.
이런 수는 따로 처리를 해서 저장을 해줘야한다.
밑의 코드에서 소인수 분해를 하고 x > 1인경우가 따로 처리한 경우이다.
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
#define MAX 3500
#define PLUS 2300
#define INF 987654321
int N, M;
int arr[1001];
int pr[10011];
vector<int> prime;
int Size;
vector<int> adj[MAX];
int C[MAX][MAX], f[MAX][MAX];
const int src = MAX - 2, sink = MAX - 1;
int level[MAX], work[MAX];
unordered_map<int, int> save;
int cnt = 0;
void init() {
int L = (int)sqrt(N) + 1;
for (int n = 2;n*n <= L;n++) {
for (int m = n*n;m <= L;m += n) pr[m] = true;
}
for (int n = 2;n <= L;n++) if (!pr[n]) prime.push_back(n);
Size = prime.size();
}
void add_edge(int u, int v, int c) {
adj[u].push_back(v);
adj[v].push_back(u);
C[u][v] = c;
}
bool bfs() {
memset(level, -1, sizeof level);
queue<int> q;
q.push(src);
level[src] = 0;
while (!q.empty()) {
int here = q.front();
q.pop();
for (auto &next : adj[here]) {
if (level[next] == -1 && C[here][next] - f[here][next] > 0) {
level[next] = level[here] + 1;
q.push(next);
}
}
}
return level[sink] != -1;
}
int dfs(int here, const int sink, int flow) {
if (here == sink) return flow;
for (int &n = work[here]; n < adj[here].size(); n++) {
int next = adj[here][n];
if (level[next] == level[here] + 1 && C[here][next] - f[here][next] > 0) {
int get = dfs(next, sink, min(flow, C[here][next] - f[here][next]));
if (get) {
f[here][next] += get;
f[next][here] -= get;
return get;
}
}
}
return 0;
}
int main() {
scanf("%d%d", &N, &M);
init();
for (int m = 0, x;m < M;m++) {
scanf("%d", &x);
for (int n = 0;n < Size;n++) {
if (x % prime[n] == 0) {
add_edge(n, m + PLUS, 1);
while (x && x % prime[n] == 0) x /= prime[n];
}
}
if (x > 1) {
if (save[x] == 0) save[x] = ++cnt;
add_edge(Size + save[x], m + PLUS, 1);
}
add_edge(m + PLUS, sink, 1);
}
for (int n = 0;n < Size;n++) add_edge(src, n, 1);
for (int n = 1;n <= cnt;n++) add_edge(src, Size + n, 1);
int ans = 0;
while (bfs()) {
memset(work, 0, sizeof work);
while (1) {
int get = dfs(src, sink, INF);
if (!get) break;
ans += get;
}
}
printf("%d\n", ans);
return 0;
}
| cs |
