题解：P14073 [GESP202509 五级] 数字选取

我这周末刚去考的五级，所以下来就把在考场上的思路顺了一下写的，考场上的思路可能有点笨，但是可以 AC。

思路：

题意：

这里题面描述的题意已经很清楚了，就是从

1

到

n

中选若干个互质的数，要选的数的数量最大。

我的方法：

用两个数组

a

和

b

，

a

用于存储要选的数，

b

用于判断这个数能不能选。

b

数组的细致作用：

一开始先把 $b$ 里面所有数标记成 $0$ ，表示可以取（ $1$ 就代表不可取）。
假如我选了 $2$ 这个数，为了保证 $a$ 数组中的数互质，就不能选 $2$ 的倍数，那这个时候就用一个 for 循环把 $2$ 的倍数都标记成 $1$ ，表示不可取，之后判断选不选那个数的时候就看看 $b_{i}$ 的值是否为 $0$ 。

细致：

首先

1

肯定要选，然后看

2

和

3

，

2

和

3

如果都选的话，那

b

数组中很多值都会被标记成

1

，不值得，所以分别考虑选

2

和选

3

。

拿选

2

来举例子：

选 $1$ 和 $2$ ，那就是： $a_i=1,a_2=2$ 。
用 for 循环遍历把 $b_{2 的倍数}$ 标记为 $1$ ：for(int i=2;i<=n;i+=2) b[i]=1;。
从 $3$ 开始便利，看是否与前一个数互质且 $b_i=0$ ，如果是的话就把这个数插入到 $a$ 数组中，同时把 $b_{i 的倍数}$ 标记成 $1$ ，同时 ans++。
最后再输出 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;
}

由于这个思路是我在考场上想到的，所以可能有点麻烦，如果有可以改进的地方希望提出。

题解：P14073 [GESP202509 五级] 数字选取

文章操作

题解：P14073 [GESP202509 五级] 数字选取

思路：

题意：

我的方法：

细致：

Code：

相关推荐

评论

题解：P14073 [GESP202509 五级] 数字选取