Description

有 \(n\) 种数字, 第 \(i\) 种数字是 \(a_i\), 有 \(b_i\) 个, 权值是 \(c_i\).

若两个数字 \(a_i, a_j\) 满足,\(a_i\) 是 \(a_j\) 的倍数, 且 \(\frac{a_i}{a_j}\) 是一个质数, 那么这两个数字可以配对, 并获得 \(c_i \cdot c_j\) 的价值.

一个数字只能参与一次配对, 可以不参与配对.

在获得的价值总和不小于 \(0\) 的前提下, 求最多进行多少次配对.

Input

第一行一个整数 n.

第二行 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\).

第三行 \(n\) 个整数 \(b_1, b_2, \ldots, b_n\).

第四行 \(n\) 个整数 \(c_1, c_2, \ldots, c_n\).

Output

一行一个数, 最多进行多少次配对

Sample Input

3
2 4 8
2 200 7
-1 -2 1

Sample Output

4

Data Range

\(n \leq 200, a_i \leq 10^9, b_i \leq 10^5, |c_i| \leq 10^5\)

Explanation

费用流, 最大或最小随意, 看你给费用的符号, 建图的话是把数分成两部分, 分别是奇数个 质因子和偶数个质因子, 然后通过题目给出的关系连边 (分部分的原因是形成二分图, 从而 分别向源点和汇点连边), 费用为 \(c_i \cdot c_j\), 流量正无穷, 然后两部分分别向源点 汇点连边, 费用 \(0\), 流量为 \(b_i\).

但是这道题毒性比较大...... 首先调了差不多一个半小时的 printf (因为不停 SIGSEGV, 所以 就去用 GDB), 结果发现在 printf 里崩溃, 横横竖竖找了好久, 发现直接用 printf 也会 出错, cout 同理, 结果把输出到处乱移结果发现数组越界...... 看来 Cygwin 和 MINGW 毕竟 没有 LXSS 靠谱.

随之而来的是大量的调试, 不停 WA 之后发现其实建图的时候就把费用的正负号写反了~ 看了这么多眼是不是眼花了所以才做不对的......

但是就只能这样了. 最后还 RE+WA 了两次, 原来是正无穷开的不够大~

明显这道题不是 1A TAT

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>

using namespace std;
typedef long long lli;
const int maxn = 500, maxm = 50010, maxp = 32010;
const lli infinit = 0x007f7f7f7f7f7f7fll;
// const lli infinit = 0x7f7f7f7f;

class SpfaMaxFlow
{
public:
    struct edge
    {
        int u, v;
        lli flow, cost;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm], *from[maxn];
    lli dist[maxn];
    bool inque[maxn];
    void add_edge(int u, int v, lli flow, lli cost)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow; p->cost = cost;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0; q->cost = -cost;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool spfa(void)
    {
        queue<int> que;
        for (int i = 1; i <= n; i++)
            dist[i] = infinit, inque[i] = false, from[i] = NULL;
        que.push(s);
        dist[s] = 0; inque[s] = true;
        bool found = false;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next) {
                if (ep->flow && dist[ep->v] > dist[p] + ep->cost) {
                    dist[ep->v] = dist[p] + ep->cost;
                    from[ep->v] = ep;
                    if (!inque[ep->v]) {
                        que.push(ep->v);
                        inque[ep->v] = true;
                    }
                }
            }
            if (p == t)
                found = true;
            inque[p] = false;
        }
        return found;
    }
    lli max_flow, min_cost;
    void eval(void)
    {
        lli flow, cost;
        max_flow = 0;
        min_cost = 0;
        while (spfa()) {
            flow = infinit;
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                flow = min(flow, ep->flow);
            cost = dist[t];
            // If cost is too small, we need to ensure there's a valid flow
            if (min_cost + cost * flow <= 0) {
                for (edge *ep = from[t]; ep; ep = from[ep->u])
                    ep->flow -= flow,
                    ep->rev->flow += flow;
                max_flow += flow;
                min_cost += cost * flow;
            } else {
                max_flow -= min_cost / cost;
                break;
            }
            continue;
        }
        return ;
    }
} graph;

int n;
lli a[maxn], b[maxn], c[maxn];

int prime_cnt;
lli prime[maxp];
bool prime_flag[maxp];
lli solo[maxp], duo[maxp];

void init_prime(void)
{
    for (int i = 2; i <= 32000; i++) {
        if (!prime_flag[i])
            prime[++prime_cnt] = i;
        for (int j = 1; j <= prime_cnt; j++) {
            lli val = i * prime[j];
            if (val > 32000)
                break;
            prime_flag[val] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
    return ;
}

bool judge(int i, int j)
{
    // Not a relation of proportional multiples
    if (!a[i] || !a[j] || (a[i] % a[j] && a[j] % a[i]))
        return false;
    int p = max(a[i] / a[j], a[j] / a[i]);
    for (int k = 1; k <= prime_cnt; k++) {
        if (prime[k] >= p)
            break;
        if (p % prime[k] == 0)
            return false;
    }
    return true;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &b[i]);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &c[i]);
    // Preprocessing numbers
    init_prime();
    solo[0] = duo[0] = 0;
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 1; j <= prime_cnt; j++) {
            lli x = a[i];
            while (x % prime[j] == 0)
                x /= prime[j], cnt++;
        }
        if (cnt & 1)
            solo[++solo[0]] = i;
        else
            duo[++duo[0]] = i;
    }
    // Building graph
    for (int i = 1; i <= solo[0]; i++)
        for (int j = 1; j <= duo[0]; j++)
            if (judge(solo[i], duo[j]))
                graph.add_edge(solo[i], duo[j], infinit, - c[solo[i]] * c[duo[j]]);
    graph.n = n + 2;
    graph.s = n + 1;
    graph.t = graph.n;
    for (int i = 1; i <= solo[0]; i++)
        graph.add_edge(graph.s, solo[i], b[solo[i]], 0);
    for (int i = 1; i <= duo[0]; i++)
        graph.add_edge(duo[i], graph.t, b[duo[i]], 0);
    // Evaluation
    graph.eval();
    lli res = graph.max_flow;
    printf("%lld\n", res);
    return 0;
}