有 种数字，第 种数字是 、有 个，权值是 。
若两个数字 、 满足， 是 的倍数，且 是一个质数，那么这两个数字可以配对，并获得 的价值。
一个数字只能参与一次配对，可以不参与配对。 在获得的价值总和不小于 的前提下，求最多进行多少次配对。
链接
题解
线性筛预处理质数（到 肯定够用了），用试除法判断质数，可以匹配的数字连边，做一遍二分图染色。
源点到所有 点连边，容量为 费用为 ；所有 点向汇点连边，容量为 费用为 ；可以匹配的数字从 点向 点连边，容量为无穷大，费用为 。
先求出整张网络的最大流作为二分的上界。然后建立超级源点，并从超级源点向源点连边，二分这条边的容量，用费用流检验，如果费用 说明可行。
代码
#include <cstdio>
#include <climits>
#include <queue>
#include <algorithm>
const int MAXN = 200;
const int MAXA = 1e9;
const int MAXP = 1e6;
struct Node;
struct Edge;
struct Node {
Edge *e, *in;
int c, f;
long long d;
bool q;
} N[MAXN + 3];
struct Edge {
Node *s, *t;
int f, c;
long long w;
Edge *next, *r;
Edge(Node *s, Node *t, const int c, const long long w) : s(s), t(t), f(0), c(c), w(w), next(s->e) {}
} *limE;
template <typename T, size_t SIZE>
struct MemoryPool {
char buf[SIZE * sizeof(T)], *cur;
MemoryPool() {
reset();
}
void reset() { cur = buf; }
T *alloc() {
if (cur == buf + SIZE * sizeof(T)) return (T *)malloc(sizeof(T));
else {
char *p = cur;
cur += sizeof(T);
return (T *)p;
}
}
};
MemoryPool<Edge, MAXN * MAXN * 10> pool;
inline Edge *addEdge(int u, int v, const int c, const long long w) {
// printf("E(%d, %d, %d, %d)\n", u, v, c, w);
N[u].e = &(*(pool.alloc()) = Edge(&N[u], &N[v], c, w));
N[v].e = &(*(pool.alloc()) = Edge(&N[v], &N[u], 0, -w));
N[u].e->r = N[v].e, N[v].e->r = N[u].e;
return N[u].e;
}
inline void edmondskarp(const int s, const int t, const int n, int &flow, long long &cost) {
flow = cost = 0;
while (1) {
for (int i = 0; i < n; i++) {
N[i].q = false;
N[i].in = NULL;
N[i].f = 0;
N[i].d = LLONG_MAX;
}
std::queue<Node *> q;
q.push(&N[s]);
N[s].d = 0, N[s].f = INT_MAX;
while (!q.empty()) {
Node *v = q.front();
q.pop();
v->q = false;
for (Edge *e = v->e; e; e = e->next) {
if (e->f < e->c && e->t->d > v->d + e->w) {
e->t->d = v->d + e->w;
e->t->in = e;
e->t->f = std::min(v->f, e->c - e->f);
if (!e->t->q) {
e->t->q = true;
q.push(e->t);
}
}
}
}
if (N[t].d == LLONG_MAX) return;
for (Edge *e = N[t].in; e; e = e->s->in) {
e->f += N[t].f;
e->r->f -= N[t].f;
}
flow += N[t].f;
cost += N[t].f * N[t].d;
// printf("cost = %d\n", -cost);
}
}
int n, s, ss, t;
struct Number {
int a, b, c, t;
bool operator<(const Number &o) const { return a < o.a; }
} a[MAXN + 1];
inline void color() {
for (int i = 1; i <= n; i++) {
if (N[i].c != 0) continue;
std::queue<Node *> q;
q.push(&N[i]);
N[i].c = 1;
while (!q.empty()) {
Node *v = q.front();
q.pop();
for (Edge *e = v->e; e; e = e->next) {
if (e->t->c == 0) {
e->t->c = (v->c == 1) ? -1 : 1;
q.push(e->t);
} else {
// if (e->t->c == v->c) throw;
}
}
}
}
}
inline bool check(const int limit) {
for (int i = 0; i < n + 3; i++) {
for (Edge *e = N[i].e; e; e = e->next) {
e->f = 0;
}
}
limE->c = limit;
int flow;
long long cost;
edmondskarp(ss, t, n + 3, flow, cost);
// printf("cost = %d\n", cost);
return cost <= 0;
}
inline int solve() {
limE->c = INT_MAX;
int flow;
long long cost;
edmondskarp(ss, t, n + 3, flow, cost);
int l = 0, r = flow;
while (l < r) {
// printf("(%d, %d)\n", l, r);
int mid = l + ((r - l) >> 1) + 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
bool isNotPrime[MAXP + 1];
int primes[MAXP], cnt;
inline void euler() {
isNotPrime[0] = isNotPrime[1] = true;
for (int i = 2; i <= MAXP; i++) {
if (!isNotPrime[i]) {
primes[cnt++] = i;
}
for (int j = 0; j < cnt; j++) {
if (primes[j] * i > MAXP) break;
isNotPrime[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
inline bool isPrime(const int x) {
if (x <= MAXP && isNotPrime[x]) return false;
if (x == 1) return false;
for (int i = 0; i < cnt; i++) {
int &p = primes[i];
if (p * p > x) return true;
if (x % p == 0) return false;
}
return true;
}
int main() {
freopen("pair.in", "r", stdin);
freopen("pair.out", "w", stdout);
euler();
scanf("%d", &n);
int sum = 0;
for (int i = 1; i <= n; i++) scanf("%d", &a[i].a);
for (int i = 1; i <= n; i++) scanf("%d", &a[i].b), sum += a[i].b;
for (int i = 1; i <= n; i++) scanf("%d", &a[i].c);
std::sort(a + 1, a + n + 1);
bool valid[MAXN + 1][MAXN + 1];
for (int i = 1; i <= n; i++) {
Number &xi = a[i];
for (int j = 1; j < i; j++) {
Number &xj = a[j];
if (xi.a % xj.a == 0 && isPrime(xi.a / xj.a)) {
valid[i][j] = true;
addEdge(i, j, 0, 0);
}
}
}
color();
for (int i = 1; i <= n; i++) {
a[i].t = N[i].c;
N[i].e = NULL;
}
pool.reset();
s = 0, ss = n + 1, t = n + 2;
for (int i = 1; i <= n; i++) {
Number &xi = a[i];
for (int j = 1; j < i; j++) {
Number &xj = a[j];
if (valid[i][j]) {
// if (xi.t == xj.t) puts("failed!");
if (xi.t == 1) {
addEdge(i, j, INT_MAX, -(long long)xi.c * xj.c);
} else {
addEdge(j, i, INT_MAX, -(long long)xi.c * xj.c);
}
}
}
if (N[i].c == 1) {
addEdge(s, i, xi.b, 0);
} else {
addEdge(i, t, xi.b, 0);
}
}
limE = addEdge(ss, s, sum, 0);
printf("%d\n", solve());
fclose(stdin);
fclose(stdout);
return 0;
}