点击蓝字
关注赵码匠
（说明：保证1≤n≤100000，每次查询满足1≤L≤R≤n，且数组a的元素均为正整数）
结合下文的题干，该程序解决的是区间查询问题，并且第25题明确为最大公约数，那么，我们大胆推测程序的功能为：
输入n个数字和m次查询，每次查询区间[L,R]内所有元素的最大公约数。
我们知道，解决区间查询问题的算法或数据结构包括：ST表、分块、线段树、树状数组、莫队算法、笛卡尔树等，本题代码属于哪一种呢？
（1）第4~8行非常简单，是标准的计算x和y的最大公约数的函数；
（2）第13行的循环，pw数组的后一项是前一项的2倍，具体推断pw[i]存储的是2的i次幂的值；
（3）第14~16行代码，模拟i=1时，pw[t+1]=pw[1]=2>1，因此lg[1]=0；
i=2时，pw[t+1]=2=2，因此t++，lg[2]=1;
i=3时，pw[t+1]=pw[2]=4<3，因此lg[3]=1；
……
后面就不一一递推了，这里的循环在通过递推公式，lg[i]计算所有log以2为底i的值。
（4）第17~18行代码，初始化dp数组dp[i][0]=a[i]，其实到这里心里就有数了，程序大概率是用ST表预处理区间最大公约数，这里dp[i][0]表示从i开始2^0个元素的最大公约数，2^0=1，因此dp[i][0]的值就是a{i]；
（5）第19~22行的代码，更加能够验证程序在预处理ST表；
外循环的次数为lg[n]次，表示区间最长为大于等于n的第一个2次幂数的指数；
内循环次数则与j有关，保证从起点i开始，长度为2^j的区间不越界；
循环体为dp数组的更新，结合我们学习过的st表维护，显然可以解读出：
dp[i][j]表示从i开始，区间长度为2^j中所有元素的最大公约数；
就等价于，从i开始、区间长度为2^(j-1)的区间最大公约数，与从i+2^(j-1)开始，区间长度为2^(j-1)的区间最大公约数，这两数的最大公约数。
简要的说，就是长度为2^j区间的值，就是两个长度为2^(j-1)区间值相互比较或计算的结果。
（6）第23~26行，根据输入的区间[L,R]输出对应的结果：
先根据区间长度R-L+1，找到最大的整数k满足2^k<R-L+1后；
待查询的区间就可以分为两部分：左区间[L, L+2^k-1]，和右区间[R-2^k+1, R]；
两个区间的最大公约数都已经在dp[i][j]数组的维护中计算完毕了，最终整个区间的最大公约数，就是左区间与右区间的结果在进行一次计算后的结果。
（7）一般来说，我们使用st表预处理，适用于解决查询区间最值、区间位运算、区间逻辑值等情况，这些都属于“可重复贡献”性质的运算操作。
“可重复贡献”指的是某个元素或区间即使被重复计算多次，也不会影响最终结果。
而本题求解的区间最大公约数，也属于“可重复贡献”问题，一个数字多次参与到最大公约数的计算，不会影响到整体的最大公约数的结果。
22. 当n=5，a={4,2,6,3,9}，且仅有一次查询L=2、R=5时，输出为1。
答案：√
解析：结合题意，这里需要查询a[2~5]区间内所有元素的最大公约数，即{2,6,3,9}的最大公约数；
我们知道{6,3,9}的最大公约数是3，但是再带上2后，最大公约数只能是1，因此题干计算正确。
23. 当某次查询的区间长度为1（即L=R）时，这次查询的输出一定等于a[L]。
答案：√
解析：当区间长度为1时，这个区间只有一个元素a[L]，从这个角度就能知道，查询的输出肯定是a[L]。
如果要跟着代码继续分析的话，由于区间长度为1，因此j=0，因此区间对应的结果为dp[i][0]，在第17~18行中将其初始化为a[L]，后续也不会变化该dp值，因此查询输出为dp[i][0]=a[L]。
从两个角度，都证明了这次查询的输出一定等于a[L]。
24. 任意一次查询的输出结果一定不小于该查询区间内的最小值。
答案：×
解析：查询的输出结果为区间最大公约数，这里直接举反例说明：
假设当前查询区间的元素为{6,9,15}，这三个数的最大公约数为3，小于区间内的最小值6，因此题干描述错误。
25. 对于j≥1，数组dp[i][j]保存的是（ ）
A、从a[i]开始连续j个数的最大公约数
B、从a[i]开始连续2^j个数的最大公约数
C、a[i]与a[j]的最大公约数
D、从a[1]到a[i]的最大公约数
答案：B
解析：本题也是我们分析程序功能的关键突破口，只要分析出题干程序为ST表，自然就知道了dp[i][j]表示从a[i]开始2^j个元素的最大公约数。
26. 若把一次求最大公约数的运算视为O(1)，则第17~22行建表过程的时间复杂度为（ ）
A、Θ(n)
B、Θ(n logn)
C、Θ(n^2)
D、Θ(mn)
答案：B
解析：分析循环情况：
（1）17~18行为一个循环，该循环次数为O(n)，非常显而易见；
（2）19~22行为一个嵌套循环，其中外循环的次数为lg[n]次，即O(log n)，内循环的次数不确定，但是最大为n+1-pw[0]=n+1-1=n次，因此为O(n)次；
综合嵌套循环，19~22行循环的操作数为O(n logn)；
综合两个循环的情况，总时间复杂度应为Θ(n logn)。
27. 设x为一次查询的区间长度（即x=R-L+1），则使得lg[x]=5的x的取值范围是（ ）
A、[16,31]
B、[17,32]
C、[32,63]
D、[33,64]
答案：C
解析：这里考察14~16行代码对lg[]数组的初始化理解。
其关键之处在于分支判断：if(pw[t+1] > i)，当i=32时，此时的t应该为4，pw[t+1]=pw[5]=32，这时候进入else，t=5，lg[32]=5；
后续的i，从33~63，都是pw[t+1]=64>i，因此lg[33~63]=5；
直到i=64时，pw[t+1]=64，这时候要进入else，t=6，lg[64]=6就不符合了。
因此使得lg[x]=5的x的取值范围是[32,63]。
这里要注意，有些版本的真题中第15行判断为“if(pw[t+1] >= i)”，此时本题的答案为[33,64]。
但是，赵码匠更倾向于这里是“>”而非“>=”，因为从数学角度来说，log以2为底32~63，其值都为5点几，log以2为底64的值是6，“>”的版本，更加符合数学计算的结果。
原创文章制作不易
欢迎大家分享到微信群、朋友圈等社交圈
如需转载，可后台留言开通白名单
注：未经允许不得私自搬运到其他平台
如果觉得写的不错的话
还请帮忙点赞、在看、关注
谢谢!
