G. Summmon题意给定数组a。对任意一个子数组b可以执行任意次操作选择 1 i m b[i 1] : b[i 1] b[i] 或者 b[i 1] : b[i 1] - b[i]记f(b)为经过若干次操作后max(b) - min(b)能达到的最小值。要求计算所有子数组的f之和sum f(a[l ... r])答案可能超过long long。先看操作本质第一个元素永远不会被改变因为没有位置能操作到它。对于一个子数组b [b1, b2, ..., bm]设当前要处理第i个数。它前面的数是b1, b2, ..., b[i - 1]通过操作第i个数可以加上或减去前面这些数凑出来的整数线性组合。根据 gcd 的性质它最终能变成的数恰好满足新值 ≡ 原值 (mod gcd(b1, b2, ..., b[i - 1]))也就是说第 i 个数能怎么调整只由它前面所有数的 gcd 决定。这是整道题最重要的观察。核心结论考虑一个子数组b [b1, b2, ..., bm]令x b1从左往右找第一个不能被x整除的位置pb[p] % x ! 0如果不存在这样的p那么f(b) 0如果存在这样的p令r b[p] % x那么f(b) min(r, x - r)一句话总结一个子数组的贡献只看首元素和后面第一个不能被首元素整除的数。为什么只看第一个不整除的位置还是设x b1。情况 1后面全是 x 的倍数如果b2, b3, ..., bm全部都是x的倍数那么可以从左到右把每个元素都调整成x。例如[6, 12, 24] - [6, 6, 6]所以此时f(b) 0情况 2出现第一个不是 x 倍数的数设p是第一个满足b[p] % x ! 0的位置。因为p前面的数都是x的倍数所以在处理b[p]之前前缀 gcd 仍然是x。因此b[p]只能变成b[p] k * x也就是所有和b[p]模x同余的数。令r b[p] % x那么b[p]离x最近的可能位置距离就是min(r, x - r)记这个值为w。所以答案至少是w。另一方面答案确实可以做到w如果r x - r把b[p]放到x r区间可以是[x, x r]。如果r x - r把b[p]放到r区间可以是[r, x]。这个区间长度正好是w。处理完b[p]后前缀 gcd 会变成g gcd(x, b[p])因为g同时整除x和b[p]所以它也整除r和x - r从而整除w。于是g w长度为w的连续整数区间里至少能覆盖模g的所有余数。后面的前缀 gcd 只会继续变成g的因子所以后面的每个元素都可以被调整进这个区间不会让答案继续变大。因此f(b) w min(b[p] % x, x - b[p] % x)如何统计所有子数组固定左端点l。令x a[l]找到最小的p l满足a[p] % x ! 0如果不存在这样的p那么所有以l开头的子数组贡献都是0。如果存在这样的p令w min(a[p] % x, x - a[p] % x)那么右端点r p时子数组a[l ... r]后面全是x的倍数贡献是0。右端点r p时第一个不整除位置都是p贡献都是w。这样的右端点有n - p 1个。所以左端点l对总答案的贡献是w * (n - p 1)怎么快速找到 p我们需要对每个l找第一个不能被a[l]整除的位置。考虑区间[l 1, mid]。这段区间里的所有数都能被a[l]整除等价于gcd(a[l 1], ..., a[mid]) % a[l] 0所以可以建一个 gcd 稀疏表支持O(1)查询区间 gcd。对每个左端点l二分第一个不满足条件的位置p。为什么可以二分如果[l 1, mid]已经包含了一个不能被a[l]整除的数那么这段区间的 gcd 也不可能再被a[l]整除。所以条件具有单调性。例子数组[6, 4, 8]按左端点统计左端点 lx a[l]第一个不被 x 整除的位置 pw贡献16p 2, a[p] 4min(4, 2) 22 * 2 424不存在因为 8 能被 4 整除0038不存在00总答案4复杂度设数组长度为n。内容复杂度建 gcd 稀疏表O(n log n)每个左端点二分O(log n)总时间复杂度O(n log n)空间复杂度O(n log n)所有测试用例的n之和不超过2 * 10^5可以通过。C 代码下面的代码没有依赖__int128或 Boost。答案用一个很小的大整数维护只需要支持加上一个long long和输出。#includebits/stdc.husingnamespacestd;usingint64longlong;structBigInt{staticconstintBASE1000000000;vectorintd;voidadd(longlongx){inti0;while(x0){if(i(int)d.size())d.push_back(0);longlongcur(longlong)d[i]x%BASE;d[i]int(cur%BASE);xx/BASEcur/BASE;i;}}stringstr()const{if(d.empty())return0;string resto_string(d.back());for(inti(int)d.size()-2;i0;i--){string partto_string(d[i]);resstring(9-part.size(),0)part;}returnres;}};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn;cinn;vectorint64a(n1);for(inti1;in;i){cina[i];}intK__lg(n)1;vectorvectorint64st(K,vectorint64(n1));for(inti1;in;i){st[0][i]a[i];}for(intk1;kK;k){intlen1k;for(inti1;ilen-1n;i){st[k][i]gcd(st[k-1][i],st[k-1][i(len1)]);}}autorange_gcd[](intl,intr)-int64{intlenr-l1;intk__lg(len);returngcd(st[k][l],st[k][r-(1k)1]);};BigInt ans;for(intl1;ln;l){if(ln)continue;int64 xa[l];intposn1;intlowl1;inthighn;while(lowhigh){intmid(lowhigh)/2;int64 grange_gcd(l1,mid);if(g%x0){lowmid1;}else{posmid;highmid-1;}}if(posn){int64 ra[pos]%x;int64 wmin(r,x-r);ans.add(w*1LL*(n-pos1));}}coutans.str()\n;}return0;}小结这题最关键的一步是不要模拟操作而是把操作转成 gcd 和同余后面的数只能在某个 gcd 模意义下移动。再利用首元素固定这一点可以进一步发现每个子数组只由第一个不被首元素整除的位置决定贡献。于是问题就变成了对每个左端点快速找到第一个不整除的位置。用 gcd 稀疏表加二分即可完成。