题意: 给出一颗树,请你找出最长的一条链,这条链上所有数值的GCD要大于1.并输出最长链的长度。
这题参考了 小熠小熠很不容易 大佬的思路。
思路就是,先建一棵树,然后从根开始搜索,这里要注意根不一定是1,要自己找根。
然后再搜索的时候,每次计算下GCD,如果GCD大于1,那么是满足条件的,我们继续往下搜索。如果等于1,那么说明当前长度不能继续变长了,我们就重置这个树链长度为1.
这种思路应该非常好理解的,就相当于暴力的搜索下去,边搜边记录答案即可。
还有一种求质因子的方式本弱还没弄明白。。。。
AC代码:
#include <bits/stdc++.h> #define int long long using namespace std; const int N=100000+100; int n,x,y,ans; int a[N],f[N]; vector<int>v[N]; void dfs(int u,int len,int w) { for(auto x:v[u]) { int gc=__gcd(a[x],w); if(gc==1) { ans=max(ans,len); dfs(x,1,a[x]); } else { ans=max(ans,len+1); dfs(x,len+1,gc); } } } signed main() { scanf("%lld",&n); for(int i=0;i<n-1;i++) { scanf("%lld%lld",&x,&y); v[x].push_back(y); f[y]=1; } int root=0; for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); if(!f[i]&&!root)root=i; } dfs(root,1,a[root]); printf("%lld\n",ans); return 0; }