LibreOJ beta R4 subset

#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

struct edge {
    int v;
    edge* next;
};

const int N = 510;

int n, ans;
ll a[N];
int match[N];
bool vis[N];
edge* g[N];

void add_edge(int u, int v);
ll gcd(ll a, ll b);
bool dfs(int u);

int main() {
//  freopen("test.in", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        for (int j = 1; j < i; ++j)
            if (gcd(a[i], a[j]) == 1 && gcd(a[i] + 1, a[j] + 1) == 1) {
                add_edge(i, j);
                add_edge(j, i);
            }
    }
    for (int i = 1; i <= n; ++i) {
        memset(vis, 0, sizeof(vis));
        if (!match[i])
            if (dfs(i))
                ++ans;
    }
    printf("%d\n", n - ans);
    return 0;
}

inline void add_edge(int u, int v) {
    static edge pool[N * N];
    static int top;
    edge* p = pool + ++top;
    p->v = v;
    p->next = g[u];
    g[u] = p;
}

ll gcd(ll a, ll b) {
    if (!b)
        return a;
    return gcd(b, a % b);
}

bool dfs(int u) {
    for (edge* p = g[u]; p; p = p->next)
        if (!vis[p->v]) {
            if (!match[p->v]) {
                match[p->v] = u;
                match[u] = p->v;
                return true;
            }
            vis[p->v] = true;
            if (dfs(match[p->v])) {
                match[p->v] = u;
                match[u] = p->v;
                return true;
            }
        }
    return false;
}