打卡信奥刷题（3347）用C++实现信奥题 P9488 ZHY 的生成树

P9488 ZHY 的生成树题目描述ZHY 有一个nnn个点的完全图点uuu与点vvv的距离为gcd⁡(u,v)\gcd(u,v)gcd(u,v)求这个完全图的最大生成树的边权之和。输入格式一个正整数nnn。输出格式一个整数表示这个最大生成树的边权之和。输入输出样例 #1输入 #14输出 #14输入输出样例 #2输入 #230输出 #2183输入输出样例 #3输入 #3100输出 #31916说明/提示本题采用捆绑测试。Subtask\text{Subtask}Subtask00\kern{3pt}0(10pts)n≤5n\le 5n≤5。Subtask\text{Subtask}Subtask11\kern{3pt}1(20pts)n≤1000n\le 1000n≤1000。Subtask\text{Subtask}Subtask22\kern{3pt}2(30pts)n≤106n\le 10^{6}n≤106。Subtask\text{Subtask}Subtask33\kern{3pt}3(40pts)n≤107n\le 10^{7}n≤107。对于所有测试数据1≤n≤1071\le n \le 10^{7}1≤n≤107。C实现#includebits/stdc.husingnamespacestd;constintN1e710;intn,m,fa[N],tot;intprime[6000100],q,x,k;boolisp[N];voidPrime(){for(registerinti2;i10000000;i){if(isp[i]0)prime[k]i;for(registerintj1;jki*prime[j]10000000;j){isp[i*prime[j]]1;if(!(i%prime[j]))break;}}}intfind(intx){if(xfa[x])returnx;elsereturnfa[x]find(fa[x]);}voidkruskal(){intcnt0;longlongsum0;for(registerintin/2;i1;--i){intlenn/i;for(intu1;prime[u]*in;u){intxfind(i),yfind(prime[u]*i);tot;if(x!y){cnt;sumi;fa[y]x;if(cntn-1){coutsum;return;}}}}}signedmain(){cinn;Prime();for(inti1;in;i)fa[i]i;kruskal();return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容