「CF364D」Ghd

2015年1月20日3,8360

John Doe offered his sister Jane Doe find the gcd of some set of numbers a.

Gcd is a positive integer g, such that all number from the set are evenly divisible by g and there isn’t such g‘ (g‘ > g), that all numbers of the set are evenly divisible by g‘.

Unfortunately Jane couldn’t cope with the task and John offered her to find the ghd of the same subset of numbers.

Ghd is a positive integer g, such that at least half of numbers from the set are evenly divisible by g and there isn’t such g‘ (g‘ > g) that at least half of the numbers from the set are evenly divisible by g‘.

Jane coped with the task for two hours. Please try it, too.

Input

The first line contains an integer n (1 ≤ n ≤ 10⁶) showing how many numbers are in set a. The second line contains space-separated integers a₁, a₂, …, a_n (1 ≤ a_i ≤ 10¹²). Please note, that given set can contain equalnumbers.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the %I64dspecifier.

Output

Print a single integer g — the Ghd of set a.

Sample test(s)

input

6
6 2 3 4 5 6

1 2	6 6 2 3 4 5 6

output

3

input

5
5 5 6 10 15

1 2	5 5 5 6 10 15

output

5

搬运hgg的题解

考虑枚举一个存在于最终答案的集合内的数x，这样子，可行的gcd的范围就变成了x的因子个数，在10^12以内，最多的因子个数只有6000多个。

对于其他元素，我们关注的只有它们和当前枚举的数x的gcd了。所以可以O(nlogC)地求出来。同时，我们可以记录cnt[i]表示和x的gcd为i的有多少个。显然只有6000级别个的cnt不会为0，我们可以非常轻松地记录下来。

现在我们直接枚举一下最终的答案是多少，只需要统计有多少个数含有这个因子即可。明显复杂度可以做到6000^2。

所以假如我们枚举了一个x，现在的复杂度是O(sqrt10^12+nlogC+6000^2)，看起来还是可以接受的。假如我们随机到的位置存在于最优解中，那么我们一定能够得出最优解。注意到我们随机一个位置有1/2的概率存在于最优解中。多随机几次即可。

#include<iostream>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,top,c[1000005];
ll ans,d[1000005],a[1000005];
ll gcd(ll a,ll b)
{
	return b==0?a:gcd(b,a%b);
}
void solve()
{
	ll x=a[((rand()<<15)+rand())%n+1],top=0;
	for(ll i=1;i*i<=x;i++)
		if(x%i==0)
		{
			d[++top]=i;
			if(i*i!=x)d[++top]=x/i;
		}
	sort(d+1,d+top+1);
	for(int i=1;i<=top;i++)c[i]=0;
	for(int i=1;i<=n;i++)
		++c[lower_bound(d+1,d+top+1,gcd(a[i],x))-d];
	for(int i=1;i<=top;i++)
		for(int j=i+1;j<=top;j++)
			if(d[j]%d[i]==0)c[i]+=c[j];
	for(int i=1;i<=top;i++)
		if(c[i]*2>=n)ans=max(ans,d[i]);
}
int main()
{
	srand(time(NULL));
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=10;i++)
		solve();
	cout<<ans<<endl;
	return 0;
}

#include<iostream>

#include<set>

#include<map>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<cmath>

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,top,c[1000005];

ll ans,d[1000005],a[1000005];

ll gcd(ll a,ll b)

{

return b==0?a:gcd(b,a%b);

}

void solve()

{

ll x=a[((rand()<<15)+rand())%n+1],top=0;

for(ll i=1;i*i<=x;i++)

if(x%i==0)

{

d[++top]=i;

if(i*i!=x)d[++top]=x/i;

}

sort(d+1,d+top+1);

for(int i=1;i<=top;i++)c[i]=0;

for(int i=1;i<=n;i++)

++c[lower_bound(d+1,d+top+1,gcd(a[i],x))-d];

for(int i=1;i<=top;i++)

for(int j=i+1;j<=top;j++)

if(d[j]%d[i]==0)c[i]+=c[j];

for(int i=1;i<=top;i++)

if(c[i]*2>=n)ans=max(ans,d[i]);

}

int main()

{

srand(time(NULL));

n=read();

for(int i=1;i<=n;i++)a[i]=read();

for(int i=1;i<=10;i++)

solve();

cout<<ans<<endl;

return 0;

}

« 「codechef」January Challenge 2015 「codechef」February Lunchtime 2015 »

hzwer.com _ Home | http://hzwer.com

「CF364D」Ghd

分类目录

热门文章

Myfriends

近期评论