P11753 [COCI 2024/2025 #5] 塔楼 / Tornjevi题目背景译自 COCI 2024/2025 #5 T3。2s,0.5G \texttt{2s,0.5G}2s,0.5G。满分为90 9090。题目描述给定正整数序列h 1 , … , h n h_1,\ldots,h_nh1​,…,hn​。对于区间[ l , r ] [l,r][l,r]我们称i iil ≤ i ≤ r l\le i\le rl≤i≤r关于[ l , r ] [l,r][l,r]是好的当且仅当h i gcd ⁡ ( h l , h l 1 , … , h r ) h_i\gcd(h_l,h_{l1},\ldots,h_r)hi​gcd(hl​,hl1​,…,hr​)。对于i ii定义f ( i ) f(i)f(i)表示所有i ii关于[ l , r ] [l,r][l,r]是好的区间中r − l 1 r-l1r−l1的最大值。对于i 1 , 2 , … , n i1,2,\ldots,ni1,2,…,n求出f ( i ) f(i)f(i)。输入格式第一行正整数n nn。第二行n nn个正整数h 1 , h 2 , … , h n h_1,h_2,\ldots,h_nh1​,h2​,…,hn​。输出格式输出n nn个正整数f ( 1 ) , f ( 2 ) , … , f ( n ) f(1),f(2),\ldots,f(n)f(1),f(2),…,f(n)。输入输出样例 #1输入 #16 3 6 6 6 1 3输出 #14 3 3 3 6 1输入输出样例 #2输入 #25 10 2 10 15 5输出 #21 3 1 1 3说明/提示数据范围对于100 % 100\%100%的数据保证1 ≤ n , h i ≤ 10 6 1\le n,h_i\le 10^61≤n,hi​≤106。子任务编号n ≤ n\len≤特殊性质得分$ 1 $100 100100$ 7 $$ 2 $5 × 10 3 5\times 10^35×103$ 11 $$ 3 $5 × 10 4 5\times 10^45×104$ 17 $$ 4 $10 6 10^6106A$ 29 $$ 5 $10 6 10^610626 2626特殊性质 Ah i ≤ 100 h_i\le 100hi​≤100。C实现#includebits/stdc.husingnamespacestd;#defineMAXN1000010intg[MAXN][21],n,b[MAXN];intansl[MAXN],ansr[MAXN];intgcd(intx,inty){return(y0?x:gcd(y,x%y));}voidinit(){for(intj1;j20;j)for(inti1;i(1j)-1n;i)g[i][j]gcd(g[i][j-1],g[i(1(j-1))][j-1]);}intquery(intl,intr){intkb[r-l1];returngcd(g[l][k],g[r-(1k)1][k]);}intask(intx,intb){intl1,rb1?x-1:n-x,ans0;while(lr){intmid(lr)/2;intnow(b1?query(x-mid,x):query(x,xmid));if(g[x][0]now)ansmid,lmid1;elsermid-1;}returnans;}intmain(){scanf(%d,n);for(inti2;i1e6;i)b[i]b[i/2]1;for(inti1;in;i)scanf(%d,g[i][0]);init();for(intin;i1;i--)ansl[i]i-ask(i,1),ansr[i]iask(i,2);for(inti1;in;i)printf(%d ,ansr[i]-ansl[i]1);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容