Codeforces 449C Jzzhu and Apples(构造)

本文主要是介绍Codeforces 449C Jzzhu and Apples(构造)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：Codeforces 449C Jzzhu and Apples

题目大意：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;
}

这篇关于Codeforces 449C Jzzhu and Apples(构造)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---