题解：P14073 [GESP202509 五级] 数字选取
_Luk_
·
·
题解
题解：P14073 [GESP202509 五级] 数字选取
我这周末刚去考的五级，所以下来就把在考场上的思路顺了一下写的，考场上的思路可能有点笨，但是可以 AC。
思路：
题意：
这里题面描述的题意已经很清楚了，就是从 1 到 n 中选若干个互质的数，要选的数的数量最大。
我的方法：
用两个数组 a 和 b，a 用于存储要选的数，b 用于判断这个数能不能选。
- 一开始先把 $b$ 里面所有数标记成 $0$，表示可以取（$1$ 就代表不可取）。
- 假如我选了 $2$ 这个数，为了保证 $a$ 数组中的数互质，就不能选 $2$ 的倍数，那这个时候就用一个 for 循环把 $2$ 的倍数都标记成 $1$，表示不可取，之后判断选不选那个数的时候就看看 $b_{i}$ 的值是否为 $0$。
###### 细致：
首先 $1$ 肯定要选，然后看 $2$ 和 $3$，$2$ 和 $3$ 如果都选的话，那 $b$ 数组中很多值都会被标记成 $1$，不值得，所以分别考虑选 $2$ 和选 $3$。
拿选 $2$ 来举例子：
1. 选 $1$ 和 $2$，那就是：$a_i=1,a_2=2$。
2. 用 for 循环遍历把 $b_{2 的倍数}$ 标记为 $1$：`for(int i=2;i<=n;i+=2) b[i]=1;`。
3. 从 $3$ 开始便利，看是否与前一个数互质且 $b_i=0$，如果是的话就把这个数插入到 $a$ 数组中，同时把 $b_{i 的倍数}$ 标记成 $1$，同时 `ans++`。
4. 最后再输出 `ans` 就好了。
#### Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a,int b){
return b==0?:gcd(b,a%b);
}
int a[100100],b[100100];//a=>选的数 b=>是否可选
int ans=0;
signed main(){
int n;cin>>n;
a[1]=1;
//选2
a[2]=2;
int k=2;//a中数的个数，插入新数时数的下标
for(int i=2;i<=n;i+=2) b[i]=1;
for(int i=3;i<=n;i++){
if(gcd(i,a[k])==1&&b[i]==0){
for(int j=i;j<=n;j+=i) b[j]=1;//选了这个数后把这个数的倍数都标记为 1
ans++;
k++;
a[k]=i;
}
}
int ans1=ans+2;//一开始的 a[1] 和 a[2] 也要算进去
//清空上一个状态
sizeof(a,0,sizeof a);
sizeof(b,0,sizeof b);
a[1]=1;
k=2;
ans=0;
//选3
a[2]=3;
for(int i=3;i<=n;i+=3) b[i]=1;
for(int i=4;i<=n;i++){
if(gcd(i,a[k])==1&&b[i]==0){
for(int j=i;j<=n;j+=i) b[j]=1;
ans++;
k++;
a[k]=i;
}
}
int ans2=ans+2;
cout<<max(ans1,ans2);
return 0;
}
```
由于这个思路是我在考场上想到的，所以可能有点麻烦，如果有可以改进的地方希望提出。