推荐食用方法：直接看本人的题面翻译即可，如有写题需要，可以交CF
这套题T3、T5质量较高，值得认真思考，T2很神仙，T1、T4相对不太出彩，你问为什么没有T6？因为蒟蒻不会
套题洛谷链接
套题CF链接
T1
题面翻译
给定一个正整数序列，每次可以将两个数替换为与之乘积相等的两个数，求任意次操作后最大的序列总和，输出总和\(*2022\)。
数据范围：\(n<=50\)，\(\prod_{i=1}^n{a_i}<=10^{12}\)
此题做法
对于两个\(>=2\)的数\(x,y\)，\(x*y>=x+y\)（当且仅当\(x=y=2\)时，等号成立）
由此我们发现，将两个\(>=2\)的数\(x,y\)，换作\(1\)，\(x*y\)，即将\(x+y\)换做\(x*y+1\)一定会更优。
故而，我们只需要将整个序列累计到一个位置上，剩下位置全部取1即可。
总结：数学结论+贪心经典证明（非此形态一定不优）
T2
题面翻译
给定一个数字\(n\)，代表\(n*n\)的网格，格子\((i,j)\)权值为\(i*j\)，从\((1,1)\)出发，每次只能向右或向下走一格。到\((n,n)\)，最大化总和。
数据范围：\(n<=10^9\)，个人认为能做到\(\sum{n<=10^8}\)，即线性复杂度，就够了，剩下部分较为神仙。
此题做法
从输入形态来看，属于小清新计数题，但是这道题实际难度也不低。
我们通过手模/小清新惯用技巧打表/对于乘法的数学直觉，猜测我们先令i+1,再令j+1（先令j+1同理），不断重复进行，可以得到最优解。
考虑证明：
对于相等的\((i,j)\)，先\(i+1\)再\(j+1\)得到\(2i^2+3i+1\)，局部上优于两步加在相同位置i取得的\(2i^2+3i\)，且此时后者所能抵达的点的最大点权\((i+2,j+1)\)，两者均可达，也就是局部保证最优的同时整体不会劣（能力有限，特别严谨的不会，可以参考这篇题解）。或者也可以用偏向数学的理解方法：和一定，差小积大，差大积小，故而始终在对角线上移动。
此时答案为\(\sum_{i=1}^n{i^2}+\sum_{i=1}^{n-1}{i*(i+1)}\)。
然后进入了此题的神仙时刻：这个数列是OEIS A002412，通项公式为\(\frac{n*(n+1)*(4n-1)}{6}\)
这是啥,不会啊
诸位可以当作一个熟知结论记一下吧。
总结:取得新的熟知结论
T3
题面翻译
给定一个序列，求有多少个连续子区间满足：区间异或和的因子数量为偶数（规定0的因子数量为奇数）。
数据范围:\(n<=2*10^5\)，\(a_i<=n\)
此题做法
暴力枚举所有区间并暴力判断肯定不行，此时枚举左右端点\(O(n^2)\)，扫描区间异或和\(O(n)\)，分解因数\(O（\sqrt{n}）\)，总计\(O(n^3\sqrt{n})\)需要优化。
首先是两个好想的优化：
每次都暴力质因数分解肯定不优，由于值域较小，我们不妨打表/预处理\(2*10^5\)内因数个数为偶数的数有哪些，存入桶即可\(O(1)\)判断。
对于每个区间都扫一遍肯定不优，我们不妨前缀和+差分做到异或和\(O(1)\)查询。
接下来复杂度阈值\(O(n^2)\)便长在了枚举所有区间上，考虑优化。
然后我们有两种方式获得新的优化：数学直觉/打表。
我们打表出因数个数为偶数的数，发现它们的补集是完全平方数。或者从数学角度理解，因子都是成对出现的，即d和\(\frac{n}{d}\)，一个数n的因子数量为奇数，说明\(\exists d，n/d=d\)，即\(d^2=n\)，n为完全平方数
由于完全平方数的数量级在\(\sqrt{n}\)，\(\sqrt{n}<n-\sqrt{n}\)，我们考虑通过补集容斥降低这一维度的数量级。即总数减去区间异或和为完全平方数的区间个数得到答案。
一个小结论：\(a\ xor\ b =c ⇔ a\ xor\ c=b\)
我们考虑固定右端点，求与之区间异或和为完全平方数的左端点个数，即\(\sum_{l=1}^r{[sum_r\ xor\ sum_{l-1}=x]}\)，x为任意完全平方数
此时我们注意到，枚举左右端点的数量级均为\(O(n)\)，判等的完全平方数x的数量级为\(\sqrt{n}\)，占据\(O(1)\)的复杂度。考虑对调左端点和完全平方数，让左端点\(O(n)\)数量级变成O(1)的判断，让\(\sqrt{n}\)的完全平方数变成枚举
我们考虑不枚举左端点，转而枚举完全平方数x，查询前缀中\(sum_l\)为\(sum_r\ xor\ x\)的出现次数，即\(\sum{cnt_{sum_r\ xor x}}\)，即可通过此题，思想类似dp的值域定义域对调
总结：观察并降低数量级，通过对调合理分配时间复杂度
T4
题面翻译
给定一个带权值的\(n*m\)网格，你可以选取一块边长为\(l\)的正方形区域当且仅当该区域的所有权值都大于等于 \(l\)，问可以选取的最大正方形区域的边长。
数据范围：\(n*m<=10^6\)
此题做法
正方形长度越长，对区间内元素的限制越强。容易发现此题的答案具有单调性，考虑二分答案转化为判定性问题。
我们考虑枚举矩阵的左上角，使用二维ST表查询矩阵最小值，就做完了。
总结：二分答案转化判定性问题可以节省很多不必要的思考
T5
题面翻译
给定 n 个点无边的无向图，连接点 u 和 v需要满足边权为 gcd(u,v)，每次操作可以连接 k条边权为 k+1的边，代价为 k+1 ，问恰好连接到 m条边的最小代价。
数据范围：\(n<=10^6\)，\(m<=\frac{n(n-1)}{2}\)
此题做法
花费k+1代价连接k条边，所连接的总边数一定为m，容易发现操作次数越少代价越小，即一次连尽量多的边，从大到小，贪心选取。
接下来考虑贪心的维护，我们需要直到有多少二元组u,v以k+1为边权，即以k+1为gcd
\(gcd(u,v)=k+1\)并不好做，考虑转化：\(gcd(\frac{u}{k+1},\frac{v}{k+1})=1\)
令\(a=\frac{u}{k+1}\)，\(b=\frac{v}{k+1}\)，则转化为了\(a,b<=\frac{n}{k+1}\)，\(\sum[gcd(a,b)=1]\)
即\(\sum_{i=1}^{\frac{n}{k+1}}phi(i)\)
然后我们通过欧拉筛预处理欧拉函数的前缀和即可。
总结：欧拉函数的应用：cnt[gcd=k] ⇒ cnt[gcd=1] ⇒欧拉函数
T6不会
蒟蒻不会，数学功底太差看不懂tj
标签：平方,frac,端点,题解,sum,枚举,此题,CF1731 From： https://www.cnblogs.com/chenruikang/p/18551923