现在的位置: 首页 > 算法 > 正文

bzoj-2082 Divine divisor

2015年11月23日 算法 ⁄ 共 2915字 ⁄ 字号 暂无评论

题意:

给出一个数N,求它最大的因子次数,以及有多少个这样的因子;

这个数很大,由不超过600个小于等于10^18的数给出;

题解:

首先对这个数进行质因数分解之后,最大的质因子次数就是第一问的答案;

第二问的答案就是最大质因子次数的质因子种类数的二的幂次-1;

这两步都是显然的,然而都是很坑的地方。。

第二问的幂次要用一个高精度加法,这个注意到就没什么了;

第一问的质因数分解如果裸分解的话,时间复杂度O(600*10^9)必然是跪的;

然而实际上,就算是MR+Rho算法也卡不过去几个点;

所以这道题一定还有一些奇怪的性质;

注意到我们可以预处理10^6次以下的质数,然后对其进行一个处理,除掉所有的10^6以下的因子;

那么此时这个数不可能有多于两个因子;

再用MR判断它是否是一个质数,这样处理之后被留下的数就一定是两个大质数相乘的形式;

再对每个数开根尝试分解这个数,排除掉p^2的形式;

因为我们实际上只关心每个质数出现了多少次,而不关心它是什么,所以我们将所有的数两两求GCD,求出GCD的就可以找到一个质因子了;

如果有剩下仍未分解的数,那么我们也将不需要分解它了,任意找两个偶数把它的两个因此扔进去计数就可以了,注意有数字相同的情况;

对质数的计数我用了hash表实现,最后只要扫一遍所有的链表就可以了;

代码:

</pre><pre name="code" class="cpp">#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 1500
#define PRE 1100000
using namespace std;
typedef long long ll;
struct HashSet
{
	#define mod 1401421
	int next[mod],val[mod],head[mod],ce;
	ll X[mod];
	int &operator [](ll x)
	{
		int index=x%mod;
		for(int i=head[index];i;i=next[i])
		{
			if(X[i]==x)
				return val[i];
		}
		X[++ce]=x;
		next[ce]=head[index];
		head[index]=ce;
		return val[ce];
	}
	#undef mod
}hash;
int pri[PRE],tot;
bool vis[PRE];
ll st[N],cov[N],siz[N],dis[N],top,len;
void init()
{
	int i,j;
	for(i=2;i<PRE;i++)
	{
		if(!vis[i])
			pri[++tot]=i;
		for(j=1;j<=tot&&pri[j]*i<PRE;j++)
		{
			vis[pri[j]*i]=1;
			if(i%pri[j]==0)
				break;
		}
	}
}
ll mul(ll x,ll y,ll mod)
{
	if(x<y)	swap(x,y);
	ll ret=0;
	while(y)
	{
		if(y&1)
		{
			ret+=x;
			if(ret>=mod)
				ret-=mod;
		}
		x+=x;
		if(x>=mod)
			x-=mod;
		y>>=1;
	}
	return ret;
}
ll pow(ll x,ll y,ll mod)
{
	ll ret=1;
	while(y)
	{
		if(y&1)
			ret=mul(ret,x,mod);
		x=mul(x,x,mod);
		y>>=1;
	}
	return ret;
}
bool check(ll u,ll t,ll now)
{
	ll s=rand()%(now-2)+2;
	s=pow(s,u,now);
	if(s==1||s==now-1)	return 1;
	for(ll i=1;i<=t;i++)
	{
		s=mul(s,s,now);
		if(s==now-1)	return 1;
	}
	return 0;
}
bool judge(ll now)
{
	if(now<2)	return 0;
	if(!(now&1))return now==2;
	ll u=now-1,t=0;
	while(!(u&1))
		u>>=1,t++;
	for(int c=1;c<=10;c++)
	{
		if(!check(u,t,now))
			return 0;
	}
	return 1;
}
void out(int cnt)
{
	ll M=1000000000;
	static ll a[N],len;
	a[1]=1;
	len=1;
	for(int i=1;i<=cnt;i++)
	{
		for(int j=1;j<=len;j++)
		{
			a[j]<<=1;
		}
		for(int j=1;j<=len;j++)
		{
			a[j+1]+=a[j]/M;
			a[j]%=M;
		}
		if(a[len+1])
			len++;
	}
	a[1]--;
	printf("%lld",a[len]);
	for(int j=len-1;j>=1;j--)
	{
		printf("%09lld",a[j]);
	}
	puts("");
}
int main()
{
	srand(140142);
	int n,m,i,j,k,x,y,ans,cnt;
	ll now,temp;
	init();
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&now);
		for(j=1;j<=tot;j++)
		{
			while(now%pri[j]==0)
				hash[pri[j]]++,now/=pri[j];
		}
		if(now==1)	continue;
		temp=sqrt(now)+0.1;
		if(temp*temp==now)
			hash[temp]+=2;
		else if(judge(now))
			hash[now]++;
		else
			st[++top]=now;
	}
	sort(st+1,st+top+1);
	memcpy(dis+1,st+1,sizeof(ll)*top);
	len=unique(dis+1,dis+top+1)-dis-1;
	for(i=1;i<=top;i++)
	{
		siz[lower_bound(dis+1,dis+len+1,st[i])-dis]++;
	}
	top=len;
	for(i=1;i<=top;i++)
		st[i]=dis[i];
	for(i=1;i<=top;i++)
	{
		for(j=i+1;j<=top;j++)
			if(i!=j&&(temp=__gcd(st[i],st[j]))!=1)
			{
				if(temp!=st[i])
					cov[i]=cov[j]=temp;
			}
		for(j=1;j<=hash.ce;j++)
		{
			if(st[i]%hash.X[j]==0)
			cov[i]=hash.X[j];
		}
	}
	for(i=1;i<=top;i++)
	{
		if(cov[i])
			hash[cov[i]]+=siz[i],hash[st[i]/cov[i]]+=siz[i];
		else
			hash[i<<2]+=siz[i],hash[i<<2|2]+=siz[i];
	}
	ans=0;
	for(i=1;i<=hash.ce;i++)
	{
		if(hash.val[i]>ans)
		{
			ans=hash.val[i];
			cnt=1;
		}
		else if(hash.val[i]==ans)
		{
			cnt++;
		}
	}
	printf("%d\n",ans);
	out(cnt);
	return 0;
}