跳至正文

1 条题解

  • 0
    @ 2026-10-2 2:21:40

    逐个验证组内数的最大公约数,避免维护整个组的乘积而发生 long long 溢出。

    #include <bits/stdc++.h>
    using namespace std;
    int n,best;vector<int>a;vector<vector<int>>groups;void dfs(int p){if(int(groups.size())>=best)return;if(p==n){best=groups.size();return;}for(int j=0;j<int(groups.size());j++){bool okay=true;for(int x:groups[j])if(gcd(x,a[p])!=1)okay=false;if(okay){groups[j].push_back(a[p]);dfs(p+1);groups[j].pop_back();}}groups.push_back({a[p]});dfs(p+1);groups.pop_back();}int main(){cin>>n;a.resize(n);for(int&x:a)cin>>x;best=n+1;dfs(0);cout<<best<<"\n";}
    
    • 1

    信息

    ID
    3897
    时间
    1000ms
    内存
    128MiB
    难度
    4
    标签
    递交数
    0
    已通过
    0
    上传者