D. Almost All Divisors(数学分解因子)

其实这题并不难啊，但是分解因子的细节一定要小心。

\(比如样例48,2是因子说明24也是因子，也就是说假如x存在\)

\(那么x一定是因子中的最小数乘上最大数\)

\(那我们现在去验证x是否存在,先拿x去整除除数表，看看是否所有除数都是x的因子\)

\(然后再去判断x的因子个数是不是等于n(确保除数表包含所有因子)\)

\(考虑到d_i<=1e6,极端情况下x=1e12(我并不确定这种情况存在)\)

\(所以我们不一个一个判断sqrt(x)内的数是否是因子，而是采取短除法\)

ll x=zu,num=0,he=1;

for(int i=1;i<=cnt;i++)//用prime[]中的质数筛选

{

	num=0;

	if(x%prime[i]==0)

	{

		while(x%prime[i]==0)	num++,x/=prime[i];

		he*=(num+1);//包含num+1个prime[i]因子

	}

}

if(x>1)	he*=2;

\(比如说48=2^4*3^1,所以组合数学嘛，从2因子可以拿0,1,2,3,4个因子，有5种可能\)

\(从3因子可以拿0，1个因子两种可能，也就是总共5*2=10个因子\)

\(因为我们不能一个都不拿或者全部都拿(除数表不包括1和x),所以是10-2=8个因子\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e6+9;

ll t,n,a[301];

int prime[100009],cnt;

bool vis[maxn+10];

void make_prime()

{

	for(int i=2;i<=maxn;i++)

	{

		if(!vis[i])	prime[++cnt]=i;

		for(int j=1;j<=cnt&&i*prime[j]<=maxn;j++)

		{

			vis[i*prime[j]]=1;

			if(i%prime[j]==0)	break;

		}

	}

}

int main()

{

	cin>>t;

	make_prime();

	while(t--)

	{

		cin>>n;

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

		sort(a+1,a+1+n);

		if(n>=2)

		{

			ll zu=a[1]*a[n],flag=1;

			for(int i=2;i<=(n+1)/2;i++)//考虑奇数中间的数，所以(n+1)/2

			{

				if(a[i]*a[n-i+1]==zu)	continue;

				flag=0;

				break;

			}

			if(flag==0)	cout<<-1;

			else

			{

				//判断zu有多少个因子

				ll x=zu,num=0,he=1;

				for(int i=1;i<=cnt;i++)//用prime[]中的质数筛选

				{

					num=0;

					if(x%prime[i]==0)

					{

						while(x%prime[i]==0)	num++,x/=prime[i];

						he*=(num+1);//包含num+1个prime[i]因子

					}

				}

				if(x>1)	he*=2;

				ll ans=0;

				if(he-2==n) 	cout<<zu;

				else	cout<<-1;

			}

		}

		else

		{

			if(vis[a[1]])	cout<<-1;

			else	cout<<a[1]*a[1];

		}

		cout<<endl;

	}

}

巴特西

D. Almost All Divisors(数学分解因子)

最新文章

热门文章