【次大gcd】#uoj #48. 【UR #3】核聚变反应强度

uoj #48. 【UR #3】核聚变反应强度

题目描述

给出一个长度为 n 的数列 a，求 a1 分别与 a1...an 的次大公约数。不存在则输出-1。

输入

第一行一个正整数 nn 。

第二行 n 个用空格隔开的正整数，第 ii 个为 aiai 。

n≤105,ai≤1012n≤105,ai≤1012
输出

一行 n 个用空格隔开的整数，第 i个表示 sgcd(a1,ai)

样例输入

4
12450 1 2 450

样例输出

6225 -1 1 75

题意：

给定a[1~n],求sgcd(a[1],a[1]),sgcd(a[1],a[2])...sgcd(a[1],a[n]);
(其中sgcd表示次大公约数，若不存在请输出-1)

sol:

根据唯一分解定理（猜结论），可知sgcd(a,b)==gcd(a,b)/a与b共有的最小质因子
暴力：每一对都枚举最大公约数再枚举最小质因数，O(n*sqrt(a))

再读一遍题，思考：每次都是用 a1 与其它数求次大公约数，而最大公约数的因子一定是两个数的因子。

因此可以直接预处理出 a1 的所有质因子，然后每次枚举判断是否成立即可。

由于质因子只有O(log?a) 个，因此时间复杂度为 O(sqrt(a1)+nlog?a)

/*
reference:
    
Date:
    2019.10.08
sol:
    
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
template <typename T>inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dwn(i,a,b) for(int i=(a);i>=(b);--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,u) for(int i=head[u];i;i=e[i].next)

const int N =1e5+10;
int n;
int a[N];
int p[N],tot_p;

#undef int
int main(){
#define int long long
    #ifdef WIN32
    freopen("","r",stdin);
    #endif
    rd(n);
    rep(i,1,n)rd(a[i]);
    int std=a[1];
    for(int i=2;i*i<=a[1];++i){
        if(a[1]%i==0){
            p[++tot_p]=i;
            while(a[1]%i==0)a[1]/=i;
        }
    }
/*  rep(i,1,tot_p)
        printf("%lld ",p[i]);
    puts("");
*/  if(a[1]>1)p[++tot_p]=a[1];
    printf("%lld ",std/p[1]);
    rep(i,2,n){
        bool flag=0;
        int gcd=__gcd(a[i],std);
        int j;
        for(j=1;j<=tot_p;++j){
            if(a[i]%p[j]==0){
                flag=1;
                break;
            }
        }
        printf("%lld ",flag?gcd/p[j]:-1);
    }
    return 0;
}

【次大gcd】#uoj #48. 【UR #3】核聚变反应强度

原文：https://www.cnblogs.com/sjsjsj-minus-Si/p/11638287.html