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

题面

题解

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

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

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

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

#include
    
     #include
     
      #include
      
       using namespace std;#define ll long longinline 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;}