牛客小白月赛 C 枚举倍数数组划分

矫情吗；* 2024-03-31 12:49 58阅读 0赞

[C-数组划分\_牛客小白月赛62 (nowcoder.com)][C-_62 _nowcoder.com]

题意：

![3c6a772ed11b43b38524abe2572cdf73.png][]

思路：

若gcd(a,b)=1，则a和b的约数没有重合

因此我们可以把a和b的约数都放两个map里，看两个map里面的数有没有重合，重合了就是NO，否则就是YES

我们可以去暴力枚举约数，也能去先去枚举因子，再去枚举倍数

前者复杂度为O(n根号n)，刚好1e8能卡过去，后者复杂度是O(nlogn)，就会快很多

Code：

枚举约数：

#include<bits/stdc++.h>
    using namespace std;
    const int mxn=1e5+10;
    int a[mxn],b[mxn],n;
    map<int,int> mp;
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",a+i),mp[a[i]]=1;
            for(int j=2;j<=sqrt(a[i]);j++){
                if(a[i]%j==0) mp[j]=1,mp[a[i]/j]=1;
            }
        }
        int f=0;
        for(int i=1;i<=n;i++){
            scanf("%d",b+i);
            if(mp[b[i]]&&b[i]!=1){f=1;break;}
            for(int j=2;j<=sqrt(b[i]);j++){
                if(b[i]%j==0){
                    if(mp[j]||(mp[b[i]/j]&&b[i]/j!=1)){f=1;break;}
                }
            }
            if(f) break;
        }
        printf("%s\n",f?"No":"Yes");
        return 0;
    }

枚举倍数：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e6+10;
    int n;
    int a[mxn],b[mxn],mp[mxn],mp2[mxn],vis[mxn],vis2[mxn];
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;
        for(int i=1;i<=n;i++) cin>>b[i],mp2[b[i]]++;
        for(int i=2;i<=1e6;i++){
            for(int j=i;j<=1e6;j+=i){
                if(mp[j]) vis[i]++;
                if(mp2[j]) vis2[i]++;
            }
        }
        int ok=1;
        for(int i=1;i<=1e6;i++){
            if(vis[i]&&vis2[i]) ok=0;
        }
        if(ok) cout<<"Yes"<<'\n';
        else cout<<"No"<<'\n';
    }

运行速度对比：

![488a604abbe347d0920088b05efaf28c.png][]

**总结：**

**1.gcd(a,b)=1，则a和b的约数没有重合**

**2.能枚举倍数就不要枚举约数**

[C-_62 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/47266/C
[3c6a772ed11b43b38524abe2572cdf73.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c9d2a90f0f844f279a3128ab8f21c518.png
[488a604abbe347d0920088b05efaf28c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/1ca2529d3e1c48deaf2f33f949eeabbf.png