Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
142822 陈家宝 互质组 C++ 通过 100 0 MS 252 KB 779 2024-04-10 13:18:57

Tests(5/5):


#include<bits/stdc++.h> using namespace std; bool f[15][15],c[15]; int a[15],n; bool check(int x){ memset(c,false,sizeof(c)); int cnt=0; for(int i=1;i<=n;i++){ if(c[i])continue; cnt++; c[i]=true; vector<int> vec; vec.clear(); vec.push_back(i); for(int j=i+1;j<=n;j++){ if(c[j])continue; bool fl=true; for(int k=0;k<vec.size();k++) if(f[vec[k]][j]){ fl=false; break; } if(fl){ vec.push_back(j); c[j]=true; } } } return cnt<=x; } int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(__gcd(a[i],a[j])!=1)f[i][j]=true; int l=1,r=n; while(l<=r){ int mid=(l+r)/2; if(check(mid))r=mid-1; else l=mid+1; } cout<<l; return 0; }


测评信息: