【UOJ#48】【UR #3】核聚变反应强度（质因数分解）

题面

题解

答案一定是\(gcd\)除掉\(gcd\)的最小质因子。

而\(gcd\)的最小值因子一定是\(a_1\)的质因子。

所以预处理出\(a_1\)的质因子，个数不会超过\(\log(a)\)个，然后就可以直接暴力了。

时间复杂度\(O(n\log(a)+\sqrt a)\)

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

#define ll long long

inline ll read()

{

	ll x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

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

	return t?-x:x;

}

int n,tot;

ll fac[100000],a[1000100];

ll Calc(ll n)

{

	if(n==1)return -1;

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

		if(n%fac[i]==0)return n/fac[i];

	return 1;

}

int main()

{

	n=read();

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

	ll x=a[1];

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

		if(x%i==0)

		{

			fac[++tot]=i;

			while(x%i==0)x/=i;

		}

	if(x>1)fac[++tot]=x;

	for(int i=1;i<=n;++i)printf("%lld ",Calc(__gcd(a[1],a[i])));

	puts("");

	return 0;

}

巴特西

【UOJ#48】【UR #3】核聚变反应强度（质因数分解）

【UOJ#48】【UR #3】核聚变反应强度（质因数分解）

题面

题解

最新文章

热门文章