正題

題目連接:https://www.luogu.com.cn/problem/P7854

---

題目大意

給出$n$數(shù)字的一個(gè)序列$a$。

現(xiàn)在要求構(gòu)造一棵樹，使得對(duì)于任意的$(x,y)$都有
$$gcd(a_x,a_y)=a_{lca(x,y)}$$

$1\le n\le 10^5,1\le a_i\le 10^6$

---

解題思路

考慮對(duì)于一個(gè)數(shù)字$a_x$，我們枚舉它的存在于$a$序列中所有約數(shù)$a_d$，考慮對(duì)于這些$a_d$如果它們之間不存在祖先關(guān)系那么顯然無解，否則我們就選擇深度最大的那個(gè)節(jié)點(diǎn)連接。

當(dāng)然枚舉約數(shù)太麻煩所以我們直接枚舉每個(gè)數(shù)的倍數(shù)。

然后這樣的話發(fā)現(xiàn)其實(shí)是有問題的，因?yàn)槲覀冎槐ＷC了$a_{lca(x,y)}|gcd(a_x,a_y)$。

但是有解時(shí)這樣構(gòu)造肯定是正確的，所以只需要考慮如何判斷這種情況的無解即可。

發(fā)現(xiàn)如果對(duì)于每一對(duì)$(x,y)$都存在$a_i=gcd(a_x,a_y)$那么就可以用上面那種情況構(gòu)造。

所以我們只需要求出每個(gè)數(shù)字作為$gcd(a_x,a_y)$出現(xiàn)的次數(shù)就好了。

記$m$為$max\{a_i\}$，那么時(shí)間復(fù)雜度就是$O(n+m\log m)$

---

解題思路

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=1e6+10,L=1e6; int n,a[N],p[N],fa[N],r[N],c[N]; long long v[N]; bool cmp(int x,int y) {return a[x]<a[y];} int main() {scanf("%d",&n);int d=0;for(int i=1;i<=n;i++)scanf("%d",&a[i]),d=__gcd(d,a[i]);for(int i=1;i<=n;i++)a[i]=a[i]/d,p[i]=i,c[a[i]]++;sort(p+1,p+1+n,cmp);int z=1;if(!c[1])return puts("-1")&0;for(int i=1;i<=L;i++){if(!c[i])continue;while(z<=n&&a[p[z]]<=i){fa[p[z]]=r[i];r[i]=p[z];z++;}for(int j=2*i;j<=L;j+=i){if(!c[j])continue;if(!r[j])r[j]=r[i];else{if(i%a[r[j]])return puts("-1")&0;r[j]=r[i];}}}for(int i=1;i<=L;i++){for(int j=i;j<=L;j+=i)v[i]+=c[j];v[i]=v[i]*v[i];}for(int i=L;i>=1;i--)for(int j=i+i;j<=L;j+=i)v[i]-=v[j];for(int i=1;i<=L;i++)if(v[i]&&!c[i])return puts("-1")&0;for(int i=1;i<=n;i++)printf("%d ",fa[i]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P7854-「EZEC-9」GCD Tree【构造】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。