Codeforces 449C Jzzhu and Apples(构造)

浏览数：22 / 时间：2015年06月11日

题目大意：Jzzhu从苹果树上获得n个苹果，标号从1~n，现在要将他们以两个为一组卖给商家，要求一组中的两个苹果的编号最大公约数大于1，分的组数尽量多。

解题思路：枚举公约数d，只枚举素数，因为合数的可以在更小的素数被枚举。将所有没用过并且编号为d的倍数的苹果拿出来，两两组队，如果个数为奇数，那么就将2d留出来。因为d>2，所以第2个肯定是2d。并且2d是2的倍数。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5;

bool iscomp[maxn+5], vis[maxn+5];

void prime_table(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (iscomp[i])
            continue;
        for (int j = i * i; j <= n; j += i)
            iscomp[j] = 1;
    }
}

int main () {
    int n;
    scanf("%d", &n);
    prime_table(n);

    vector<int> g;
    vector<pii> ans;

    for (int i = n / 2; i > 1; i--) {
        if (iscomp[i])
            continue;
        g.clear();

        for (int j = i; j <= n; j += i) {
            if (vis[j] == 0)
                g.push_back(j);
        }
        if (g.size() & 1)
            swap(g[1], g[g.size()-1]);
        for (int i = 0; i < g.size() - 1; i += 2) {
            ans.push_back(make_pair(g[i], g[i+1]));
            vis[g[i]] = vis[g[i+1]] = 1;
        }
    }

    printf("%lu\n", ans.size());
    for (int i = 0; i < ans.size(); i++)
        printf("%d %d\n", ans[i].first, ans[i].second);
    return 0;
}