题目大意
给定一个长度为$2n(n \le 100000)$的序列，序列中每个元素$\in [1,10^9]$
让你从中选出$n$个元素，使这$n$个元素的$\gcd$最大
解题报告
我们随机选两个数的话，失败的概率为$\frac{3}{4}$
于是我们选$30 \sim 50$次的话，错误的概率就足够小了
于是我们就随机选几对数，然后求$\gcd$
之后枚举$\gcd$的因数，去更新答案
时间复杂度：$O($跑得过$)$
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200009;
const int M = 1000009;
const int TIMES = 30;
const double EPS = 0.5;
int n,tp,tot,vis[M],pri[M],cnt[N];
LL arr[N],que[N],ans=1; set<LL> VIS;
inline LL read() {
char c=getchar(); LL f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
LL GCD(LL a, LL b) {
return b? GCD(b, a%b): a;
}
bool DFS(int t, LL v) {
if (t > tot) {
if (v <= ans || VIS.count(v)) return 1;
int ret = 0; VIS.insert(v);
for (int i=1;i<=n;i++) ret += (arr[i] % v == 0);
if (ret >= (n >> 1)) {ans = v; return 1;}
else return 0;
} else {
bool ret = 0;
for (int i=0;i<=cnt[t];i++,v*=que[t]) {
if (!DFS(t+1, v)) break;
else ret = 1;
} return ret;
}
}
int main() {
freopen("apple.in","r",stdin);
freopen("apple.out","w",stdout);
srand(19260817);
for (int i=2;i<M;i++) {
if (!vis[i]) pri[++tp] = i;
for (int j=1;j<=tp&&pri[j]*i<M;j++) {
vis[i*pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
n = read();
for (int i=1;i<=n;i++) arr[i] = read();
for (int i=2;i<=n;i++) swap(arr[i], arr[rand()%(i-1)+1]);
for (int a,b,kk=1;kk<=TIMES;kk++) {
a = rand() % n + 1; b = rand() % n + 1;
LL gcd = GCD(arr[a], arr[b]); tot = 0;
for (int i=1,v;i<=tp&&(v=pri[i])<=gcd;i++) {
if (gcd % v != 0) continue;
que[++tot] = v; cnt[tot] = 0;
for (;gcd%v==0;++cnt[tot]) gcd /= v;
}
if (gcd != 1) que[++tot] = gcd, cnt[tot] = 1;
DFS(1, 1);
}
printf("%lld\n",ans);
return 0;
}
With havin so much content do you ever run into any issues of plagorism or copyright violation? My site has a lot of unique content I’ve either written myself or outsourced but it appears a lot of it is popping
it up all over the web without my agreement. Do you know any methods to help protect against content
from being ripped off? I’d certainly appreciate it.
Link exchange is nothing else except it is just placing the other person’s webpage
link on your page at appropriate place and other person will also do similar
in favor of you.
For most up-to-date information you have to visit the web and
on world-wide-web I found this website as a best web page for
most recent updates.
If some one needs expert view about blogging and
site-building then i recommend him/her to visit this web site, Keep up the nice work.
My brother recommended I might like this web site. He was
entirely right. This post truly made my day. You cann’t imagine simply
how much time I had spent for this info! Thanks!
magnificent points altogether, you just won a brand new reader.
What may you suggest in regards to your put up that you just made
a few days ago? Any positive?
Does your website have a contact page? I’m having
trouble locating it but, I’d like to send you an email.
I’ve got some recommendations for your blog you might be interested in hearing.
Either way, great site and I look forward to seeing it expand over time.
Excellent way of telling, and pleasant article to obtain information about my
presentation topic, which i am going to deliver in institution of higher education.
Genuinely no matter if someone doesn’t be aware of then its up to other viewers that they will
help, so here it happens.
Way cool! Some extremely valid points! I
appreciate you writing this post and also the rest of the
website is really good.
I couldn’t resist commenting. Well written!
I love your blog.. very nice colors & theme. Did you design this website yourself or did you hire someone to do it for you? Plz answer back as I’m looking to design my own blog and would like to find out where u got this from. thank you
Hello, i read your blog from time to time and i own a similar one and
i was just wondering if you get a lot of spam responses?
If so how do you protect against it, any plugin or anything you can suggest?
I get so much lately it’s driving me insane so any support is very much appreciated.
This paragraph is actually a pleasant one it helps new internet people,
who are wishing in favor of blogging.
Everyone loves what you guys are usually up too. This
kind of clever work and reporting! Keep up the fantastic works guys I’ve incorporated you guys
to my blogroll.
Hello, I enjoy reading through your article post. I like to
write a little comment to support you.
If you are going for most excellent contents like I do,
just visit this website all the time as it gives feature contents, thanks
Hi there! I know this is somewhat off topic but
I was wondering if you knew where I could locate a captcha plugin for my comment form?
I’m using the same blog platform as yours and I’m having difficulty finding
one? Thanks a lot!
Hello would you mind sharing which blog platform you’re working with?
I’m going to start my own blog soon but I’m having a difficult time making a decision between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your layout seems different then most blogs and I’m looking for something completely
unique. P.S Apologies for being
off-topic but I had to ask!
Hi there, i read your blog occasionally and i own a similar one and i was
just wondering if you get a lot of spam remarks? If so how do you reduce it, any plugin or anything you
can advise? I get so much lately it’s driving me mad
so any help is very much appreciated.
I like this post, enjoyed this one appreciate it for putting up.