网站的文章标题太短怎么弄,建设农垦网站,域名还在备案可以做网站吗,怎么免费注册企业邮箱正题
luogu CF364D 题目大意
给你一个大小为n的集合#xff0c;选择一个至少为一半的子集#xff0c;另其gcd最大 解题思路
由于数字个数很多#xff0c;考虑随机
随机选10个数#xff0c;对于每个数#xff0c;先处理出约数#xff0c;然后求出所有数和当前数的gcd选择一个至少为一半的子集另其gcd最大 解题思路
由于数字个数很多考虑随机
随机选10个数对于每个数先处理出约数然后求出所有数和当前数的gcd这些gcd的约数权值全部加1权值意义为gcd为这个点集合最多选多少个点最后找到最大满足权值大于一半数即可
求出10个数的答案之后求个max即可因为集合大于一半所以正确率为 1−12101-\frac{1}{2^{10}}1−2101
时间复杂度为 O(nd2)O(nd^2)O(nd2)随机的数再多就会TLE了 code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 1001000
using namespace std;
int n,w,now,v[N];
ll x,ans,a[N],s[N];
void get(ll x)
{w0;for(ll i1;i*ix;i)if(x%i0){w,s[w]i,v[w]0;if(x/i!i)w,s[w]x/i,v[w]0;}sort(s1,s1w);return;
}
ll gcd(ll x,ll y)
{return (y?gcd(y,x%y):x);
}
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%lld,a[i]);for(int g1;g10;g){xa[rand()*rand()%n1];get(x);for(int i1;in;i){nowlower_bound(s1,s1w,gcd(x,a[i]))-s;v[now];}for(int i1;iw;i)for(int ji1;jw;j)if(s[j]%s[i]0)v[i]v[j];for(int iw;i0;--i)if(v[i](n1)/2)ansmax(ans,s[i]);}printf(%lld,ans);return 0;
}
