显然，$sgcd(x,y)|gcd(x,y)$.
那么，$sgcd(x,y)=\frac{gcd(x,y)}{p[gcd(x,y)]}$
其中 $p[x]$ 表示 $x$ 的最小非 1 质因子.
那么我们可以先把 $gcd(a[1],a[i])$ 都求出来，然后枚举这个最小质因子.
因为 $gcd(a[1],a[i])$ 一定都是 $a[1]$ 的因数，所以只需要预处理 $a[1]$ 的所有质因子就行了.
然后由于一个数本质不同的质因子最多只有 $\log n$ 个，所以暴力枚举就行了.
code:
#include <bits/stdc++.h>
#define N 100009
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
ll a[N],b[N],g[N];
ll gcd(ll x,ll y)
{
return y?gcd(y,x%y):x;
}
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
ll rd()
{
ll x=0; char c;
while(c<48) c=nc();
while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc();
return x;
}
int main()
{
// setIO("input");
int n=(int)rd(),cnt=0;
for(int i=1;i<=n;++i) a[i]=rd();
for(int i=1;i<=n;++i) g[i]=gcd(a[i],a[1]);
ll x,y,z;
for(int i=2;i<=1000000;++i)
{
if(a[1]%i==0)
{
b[++cnt]=i;
while(a[1]%i==0) a[1]/=i;
}
}
if(a[1]>1) b[++cnt]=a[1];
sort(b+1,b+1+cnt);
for(int i=1;i<=n;++i)
{
int flag=0;
for(int j=1;j<=cnt;++j)
if(g[i]%b[j]==0) {
printf("%lld ",g[i]/b[j]),flag=1;
break;
}
if(!flag) printf("-1 ");
}
return 0;
}
原文链接: https://www.cnblogs.com/guangheli/p/13065630.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/353879
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
