链接： https://codeforces.com/contest/1780
\(B\)
一个显然但是不会证明的结论是分成段数尽可能少时\(gcd\)会取到极大值，也就是说这道题里面分成两段一定可以取到最大，所以枚举切割点即可。
\(C\)
用堆来维护每次座位的最大值即可。
\(D\)
交互题
题意：
限\(30\)次操作内，每次可以减去一个正整数，每次操作后都会告诉我们当前这个数二进制下\(1\)的个数，要还原出原始的数。
解法：
观察发现，如果减去某个\(2^k\)后（即二进制下的\(1000...000\)），\(1\)的个数有可能变多或者不变，也有可能变少，如果变少那就说明当前数在该位是\(1\)，否则说明这个位是\(0\)，而且可以通过增多的\(1\)的数量来反推当前位置往前多少位才到\(1\)。
此时每次操作我们忽略最后的一段连续的\(0\)（因为这个我们一直都会知道），就相当于每次都在最后\(-1\)，如果变少那就往前走，否则就\(-1000...000\)，其中\(0\)的个数是我们推到出来原来有多少位（设为\(p\)）连续的\(0\)，上次操作已经\(-1\)，所以现在剩下\(p\)个\(1\)，又考虑到下次勘探操作又要\(-1\)，所以将这次消灭操作和勘探操作合并，变成\(-1000...000\)，其中有\(p\)个\(0\)。
这样做我们可以保证一位最多操作\(1\)次，而最坏的情况是\(1010...1010\)，也是不会超过\(30\)的。
本题还有其他的理解方法，但是都大同小异，作为一道简单的交互题，还是很有启发意义的。
\(E\)
整数分块，\(gcd\)
\(F\)
莫比乌斯反演
\(G\)
后缀树组SA，后缀自动机SAM
标签：846,...,个数,Codeforces,每次,000,操作,Div,1000 From： https://www.cnblogs.com/sfcn/p/17101297.html