seo如何推广网站,wordpress靶机下载网站,链家网站开发技术,长春网站优化指导正题
题目连接:https://www.luogu.com.cn/problem/P7854 题目大意
给出nnn数字的一个序列aaa。
现在要求构造一棵树#xff0c;使得对于任意的(x,y)(x,y)(x,y)都有 gcd(ax,ay)alca(x,y)gcd(a_x,a_y)a_{lca(x,y)}gcd(ax,ay)alca(x,y) 1≤n≤105,1≤ai≤1061\leq n\leq…正题
题目连接:https://www.luogu.com.cn/problem/P7854 题目大意
给出nnn数字的一个序列aaa。
现在要求构造一棵树使得对于任意的(x,y)(x,y)(x,y)都有 gcd(ax,ay)alca(x,y)gcd(a_x,a_y)a_{lca(x,y)}gcd(ax,ay)alca(x,y)
1≤n≤105,1≤ai≤1061\leq n\leq 10^5,1\leq a_i\leq 10^61≤n≤105,1≤ai≤106 解题思路
考虑对于一个数字axa_xax我们枚举它的存在于aaa序列中所有约数ada_dad考虑对于这些ada_dad如果它们之间不存在祖先关系那么显然无解否则我们就选择深度最大的那个节点连接。
当然枚举约数太麻烦所以我们直接枚举每个数的倍数。
然后这样的话发现其实是有问题的因为我们只保证了alca(x,y)∣gcd(ax,ay)a_{lca(x,y)}|gcd(a_x,a_y)alca(x,y)∣gcd(ax,ay)。
但是有解时这样构造肯定是正确的所以只需要考虑如何判断这种情况的无解即可。
发现如果对于每一对(x,y)(x,y)(x,y)都存在aigcd(ax,ay)a_{i}gcd(a_x,a_y)aigcd(ax,ay)那么就可以用上面那种情况构造。
所以我们只需要求出每个数字作为gcd(ax,ay)gcd(a_x,a_y)gcd(ax,ay)出现的次数就好了。
记mmm为max{ai}max\{a_i\}max{ai}那么时间复杂度就是O(nmlogm)O(nm\log m)O(nmlogm) 解题思路
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N1e610,L1e6;
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 d0;for(int i1;in;i)scanf(%d,a[i]),d__gcd(d,a[i]);for(int i1;in;i)a[i]a[i]/d,p[i]i,c[a[i]];sort(p1,p1n,cmp);int z1;if(!c[1])return puts(-1)0;for(int i1;iL;i){if(!c[i])continue;while(zna[p[z]]i){fa[p[z]]r[i];r[i]p[z];z;}for(int j2*i;jL;ji){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 i1;iL;i){for(int ji;jL;ji)v[i]c[j];v[i]v[i]*v[i];}for(int iL;i1;i--)for(int jii;jL;ji)v[i]-v[j];for(int i1;iL;i)if(v[i]!c[i])return puts(-1)0;for(int i1;in;i)printf(%d ,fa[i]);return 0;
}
