打卡信奥刷题（3084）用C++实现信奥题 P7091 数上的树

P7091 数上的树题目背景本题自动开启 O2 优化时间限制 2s。题目描述您需要构造一棵二叉树根节点权值为nnn每个节点都有222个或000个儿子且满足如下限制若该点有两个儿子该点权值需等于两个儿子的权值之积。若该点没有儿子则该节点权值需为质数。同时会给出mmm条限制aia_iai​表示树上的权值不能出现aia_iai​。您构造的二叉树需要使令kkk为节点数∑i1k∑jikvallca(i,j)\sum\limits_{i1}^k\sum\limits_{ji}^kval_{lca(i,j)}i1∑k​ji∑k​vallca(i,j)​最小其中valival_ivali​表示第iii个点的权值lca(i,j)lca(i,j)lca(i,j)表示i,ji,ji,j的最近公共祖先。输入格式第一行两个正整数n,mn,mn,m。之后一行mmm个数aia_iai​。输出格式一行一个数表示最小的∑i1k∑jikvallca(i,j)\sum\limits_{i1}^k\sum\limits_{ji}^kval_{lca(i,j)}i1∑k​ji∑k​vallca(i,j)​。无解输出-1。输入输出样例 #1输入 #14 0输出 #120输入输出样例 #2输入 #212 1 4输出 #2127输入输出样例 #3输入 #3192 1 2输出 #3-1说明/提示样例解释样例111最优方案如下其中黑色数字代表权值红色数字代表标号您不需要对树标号这里的标号只是为了更方便解释样例。ansvallca(1,1)vallca(1,2)vallca(1,3)vallca(2,2)vallca(2,3)vallca(3,3)ansval_{lca(1,1)}val_{lca(1,2)}val_{lca(1,3)}val_{lca(2,2)}val_{lca(2,3)}val_{lca(3,3)}ansvallca(1,1)​vallca(1,2)​vallca(1,3)​vallca(2,2)​vallca(2,3)​vallca(3,3)​val1val1val1val2val1val3~~~~~~~~val_1val_1val_1val_2val_1val_3val1​val1​val1​val2​val1​val3​44424220~~~~~~~~4442422044424220Subtask 15 分n≤20n\leq 20n≤20。Subtask 212 分n≤106n\leq 10^6n≤106。Subtask 328 分n≤1012n\leq 10^{12}n≤1012。Subtask 420 分m0m0m0。Subtask 535 分n≤1015n\leq 10^{15}n≤1015。对于所有数据2≤n≤10152\leq n\leq 10^{15}2≤n≤10150≤m≤min⁡(n,105)0\leq m\leq \min(n,10^5)0≤m≤min(n,105)2≤ai≤n2\leq a_i\leq n2≤ai​≤n 且答案不超过4×10184\times 10^{18}4×1018。C实现#includecstdio#includealgorithm#includemap#includecmathusingnamespacestd;#definereregisterlonglongn,pri[1000002],num[1000002],dp[1000002];maplonglong,boolvis;maplonglong,intpos;intcntt,cnttt,m,cnt;inlineintdfs(relonglongx){if(pos.count(x))returnpos[x];reintxxsqrt(x);pos[x]cntt;reintycntt;dp[y]4e18;for(reinti1;icntpri[i]xx;i){cnttt;if(x%pri[i]0){reintlsdfs(pri[i]),rsdfs(x/pri[i]);num[y]num[ls]num[rs]1;dp[y]min(dp[y],(num[ls]1)*(num[rs]1)*xdp[ls]dp[rs]);}}if(!num[y])num[y]1,dp[y]x;if(vis.count(x))dp[y]4e18;returny;}signedmain(){scanf(%lld%d,n,m);relonglongx;for(reinti1;im;i)scanf(%lld,x),vis[x]1;if(vis.count(n))returnputs(-1),0;reintxxsqrt(n);for(reinti2;ixx;i)if(n%i0)pri[cnt]i;dfs(n);printf(%lld,dp[pos[n]]4e18?-1:dp[pos[n]]);}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容