【2020年牛客暑假第四场】H题 Harder Gcd Problem

传送门: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++)
// const ll mod = 1e9 + 7;const int maxn = 2e5 + 10;
// const double eps = 1e-6;
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
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
##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 协议。转载请注明出处!