[ARC118C] Coprime Set 题解

题目传送门（洛谷）
题目传送门（atcoder）

Step 1 理解题意

• 输入一个数 n n n 要求你构造一个长度为 n n n 的数组，使得其满足以下条件：
• 1. 对于任意一个 a i a_i ai​ ( 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n ) ， 1 ≤ a i ≤ 10000 1 \le a_i \le 10000 1≤ai​≤10000。
• 2. 任意两个数 a i a_i ai​ 和 a j a_j aj​ ( 1 ≤ i , j ≤ n 1 \le i,j \le n 1≤i,j≤n) 之间， 1 ≤ g c d ( a i , a j ) 1 \le gcd(a_i,a_j) 1≤gcd(ai​,aj​)。
• 3. 对于所有数 1 = g c d ( a 1 , a 2 , . . . , a n ) 1 = gcd(a_1,a_2,...,a_n) 1=gcd(a1​,a2​,...,an​)。
• 4. a a a 中的元素不能有重复！！

Step 2 题目分析

分析样例得：

• 考虑到 ( 3 ≤ n ≤ 2500 3 \le n \le 2500 3≤n≤2500 )，先构造当 n = 3 n = 3 n=3 时的结果，发现 6 , 10 , 15 6,10,15 6,10,15 是一组正解。
• 那么继续分析，发现 6 , 10 , 15 , 12 6,10,15,12 6,10,15,12 ， 6 , 10 , 15 , 12 , 20 6,10,15,12,20 6,10,15,12,20 等均为正解，那么就可以将 6 , 10 , 15 6,10,15 6,10,15 的倍数全部都扔到一个 vector 中，最后进行排序即可。

Step 3 注意事项

1. 当 n = 3 n = 3 n=3 是需要进行特判，否则将会得到 6 , 10 , 12 6,10,12 6,10,12 的错解而不是 6 , 10 , 15 6,10,15 6,10,15
2. 对于得到的每个数字都要判断是否出现过，否则出现重复项将会喜提 Wa。

Step 4 Ac code

#import <bits/stdc++.h>
using namespace std;
const int maxn=1e7+10;

vector<int>p;
bitset<maxn>vis;

int main() {
	int n;
	cin>>n;
	if(n==3) {cout<<"6 10 15";return 0;}
	for (int i=1;i<=maxn/6;i++)		if(!vis[i*6])	p.push_back(i*6),vis[i*6]=1;
	for (int i=1;i<=maxn/10;i++)	if(!vis[i*10])	p.push_back(i*10),vis[i*10]=1;
	for (int i=1;i<=maxn/15;i++)	if(!vis[i*15])	p.push_back(i*15),vis[i*15]=1;
	sort(p.begin(),p.end());
	for (int i = 0; i < n;i++)
	cout<<p[i]<<' ';
}