传送门:https://ac.nowcoder.com/acm/contest/5669/H
题意
给你T组数据,每组给一个n,找到两个集合A,B使得两个集合的元素个数相同并且没有交集并且元素<=n。然后尽量使得A和B中的相对应的元素的gcd>1的组数越多越好,先输出gcd>1的组数,在输出A和B中对应的两个数。
思路
要使的组数更多,那么就先把<=n的素数筛选出来(埃式筛法即可),然后我们将每个素数和他的倍数将其匹配,如该素数和<=n的倍数的个数为偶数,那么就就将其一一匹配,如果该素数和<=n的倍数的个数为奇数,那么就将该素数的两倍留下,然后剩下的一一匹配,到最后,就剩下一堆2*某个素数的数,因为他们有公共的公约数2,gcd>2,所以将他们一一匹配,这样就可以做到组数最大。
注意:应该从n/2往前遍历,因为越大的素数,他的倍数的个数越少。任何一个数都可以由一个素数和任意一个数相乘得到,所以只要n/2往前遍历一遍就可以将2~n的所有数遍历到,没有遍历的数就是不可以组成的组数。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
| ##include using namespace std; typedef long long ll; typedef long double ld; typedef pair pdd; ##define INF 0x7f7f7f ##define mem(a,b) memset(a , b , sizeof(a)) ##define FOR(i, x, n) for(int i = x;i <= n; i++) int n; bool is_prime[maxn + 1]; bool vis[maxn + 1]; void sieve() { mem(is_prime, true); is_prime[1] = false; for (int i = 2; i * i <= maxn; i++) { if (is_prime[i]) { for (int j = 2 * i; j <= maxn; j += i) is_prime[j] = false; } } } void solve() { cin >> n; vector v; vector tmp; mem(vis, 0); for (int i = n / 2; i >= 2; i--) { if (!is_prime[i]) continue; tmp.clear(); for (int j = i; j <= n; j += i) { if (vis[j]) continue; tmp.push_back(j); } if (tmp.size() & 1) { swap(tmp[1], tmp[tmp.size() - 1]); } for (int j = 0; j < tmp.size() - 1; j += 2) { v.push_back(make_pair(tmp[j], tmp[j + 1])); vis[tmp[j]] = 1; vis[tmp[j + 1]] = 1; } } cout << v.size() << endl; for (int i = 0; i < v.size(); i++) { cout << v[i].first << " " << v[i].second << endl; } }
signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); ##ifdef FZT_ACM_LOCAL ##else ios::sync_with_stdio(false); int T = 1; cin >> T; sieve(); while (T--) solve(); ##endif return 0; }
|
本文作者:jujimeizuo
本文地址: https://blog.jujimeizuo.cn/2020/07/26/2020-nowcoder-shujia-4-h/
本博客所有文章除特别声明外,均采用 CC BY-SA 3.0 协议。转载请注明出处!