CF1848
C
看到形如对 \(a,b\) 进行任意操作，将 \(a,b\) 替换成 \(a,b\) 的线性组合，进行到 \(0\)，显然需要考虑 \(\gcd\) 但我没考虑
\(\gcd\) 不变，考虑同时除以 \(\gcd\)，最后情况必然是 \((0,d)\rightarrow(d,d)\rightarrow(d,0)\) 长度为三的循环，那么操作到 \(0\) 的次数模 \(3\) 余数相等。
还是没法做，关注 除以 \(\gcd\)，那么不可能 \(a,b\) 同时为偶数，继而关注 奇偶性，一定有 \(01\rightarrow 11\rightarrow 10\) 的循环，而 \(a=0\) 属于 \(01\) ，直接判断奇偶性即可。
可以发现除以奇质数不影响奇偶性，那么可以仅除以 \(\gcd\) 中 \(2\) 次幂部分去除，使用 __builtin_ctz 函数，时间复杂度 \(\mathcal{O}(\sum n)\) 。
或者不需要上面的性质，考虑如何优化暴力，也就是 加速模拟，减少操作次数 。猜暴力是对的，发现不对，对于 \(a,b\) 差距过大不行，针对这种情况优化。
设 \(a\) 远大于 \(b\)，则 \((a,b)\rightarrow (b,a-b)\rightarrow (a-b,a-2b),\rightarrow (a-2b,b)\)，\(b\) 也同理，那么每次可以将较大数限制在较小数的 \(2\) 倍以内，复杂度类似辗转相除法。
总结：看到 \(a,b\) 同时除以 \(\gcd\)，想到 奇偶性
D
最优化问题，考虑最优 / 不优情况。考虑贪心，操作的 顺序，只能是先操作 \(s\)，再操作 \(C\) 更优，证明考虑反证。关注操作 \(1,2\) 的分界点，也就是最后一个操作，设 \(d\equiv s\pmod{10}\)，考虑操作 \(s\) 优于操作 \(c\) 的条件：\(d(k-i)-s>0\)，表示当前操作 \(s\) 与操作 \(c\) 贡献的差。考虑如果在前缀 \(i\) 停止操作 \(s\)，那么答案为 \(a_0+\sum\limits_{j=1}^{i}c_j\)，其中 \(a_0\) 表示一开始就操作 \(c\)，即 \(ks\)，\(c_j\) 表示操作 \(s\) 到 \(j\) 和到 \(j-1\) 的 差分，也就是我们对答案差分，求最大前缀。关注条件，设函数 \(f_i=d(k-i)-s\)，我们想要二分，发现其并无单调性，因为 \(d\) 不同。关注 \(d\)，找到 \(d\) 构成的环。考虑它能否二分。我们关注一个环的 \(c\) 的和 \(s\)，发现 \(s\) 单调下降，因为对应的 \(d\) 单调下降。我们猜测其最大前缀必然在 \(+,+,-\) 中第二个加和第三个减出现。考虑反证法。设 \(s_1,s_2,s_3\) 分别表示这三个环的和，有 \(s_1\ge s_2\ge s_3\)，设 \(s_1\) 中位置 \(p\) 最大，设 \(p\) 在 \(s_1\) 的后面部分必然小于 \(0\)，否则可以拓展，更优，\(p\) 在 \(s_1\) 的前面部分必然大于 \(0\) 。考虑 \(s_2\) 中 \(p\) 的对应位置 \(p'\)，由于对应位置单调下降，那么 \(p’\) 在 \(s_2\) 中后面部分必然小于 \(p\) 在 \(s_1\) 中后面部分，小于 \(0\) 。由于 \(s_2>0\)，则 \(p'\) 在 \(s_2\) 中前面部分大于 \(0\) ，且它与 \(p\) 在 \(s_1\) 中后面部分相加大于 \(0\) ，那么调整到 \(p'\) 必然更优，得证。
二分即可，复杂度 \(\mathcal{O}(nm\log{\frac{V}{m}})\)，其中 \(m\) 表示循环节长度，这里 \(m=4\) 。
标算做法：考虑模为 \(10\)，那么循环节唯一 \(\{2,4,8,6\}\) ，枚举对应位置，设关于循环节个数 \(x\) 的二次函数，求顶点即可，复杂度 \(\mathcal{O}(nm)\)
总结：这题的核心在于观察到循环节对应位置具有单调性 / 凸性，可以对循环节二分。直接二分不可做时，考虑 特殊二分，如：分块二分，分组二分等。
其他算法不能直接应用时，应考虑变形，对特殊情况考虑性质，是否适用。
对式子分析：
- 恒等变形
- 分离变量，关注某些变量
- 观察单项式的性质（单调性，奇偶性，周期性等）
- 观察若干单项式组合的性质（结构相同等）
- 记号变形
类似例题 ARC123 E，非常巧妙的一道题
E
由于 \(X\) 可达 \({10^6}^{10^5}\)，这显然是不可做的。而 \(X_i\le 10^6\) 又非常小，关注 \(X_i\) 。考虑 \(a\) 合法的条件，具体化，用数学语言描述，设 \(l\) 表示步数，则 \((2a-l+1)l=2X\)，由于我们要求 \(a\)，则分离变量 \(a\)，有 \(a=\frac{1}{2}(\frac{2x}{l}+l-1)\)，接下来将对 \(a\) 计数，转化为对使 \(a\) 合法的 \(l\) 计数，那么只需要后面部分为偶数即可，容易发现有两种情况：
- \(l\) 为奇数
- 设 \(2x=z2^k\)，其中 \(z\) 为奇数，则 \(l=2^ky\)，其中 \(y\mid z\) 。
如果直接统计，那么答案就是 \(2\times c\)，\(c\) 表示 \(X\) 的奇因数的个数，观察样例，显然不对，更确切的说，答案就是 \(c\) 。
我们并没有对两类中可能使 \(a\) 相等的 \(l\) 作区分，\(a\) 相等等价于 \(l+\frac{2x}{l}\) 相等。为了更好的考虑问题，我们将其视为关于 \(l\) 的双曲函数，也是对勾函数。
对勾函数：\(y=ax+\frac{b}{x}\)
问题转化为了关注函数图像中 \(y\) 相等的两点，我们只需关注转折点的横坐标 \(X_p:\sqrt{\frac{b}{a}}=\sqrt{2X}\) 。这里 \(l\) 需要满足 \(l\mid 2X\) 。考虑什么情况下 \(p,q\) 的函数值相同，发现若 \(pq=2X\)，则它们的函数值相等，且各自分布在 \(\sqrt{2X}\)，也就是转折点的两边。考虑上面的情况发现若 \(y\) 为奇因数，则 \(\frac{2X}{y}\) 必然有因数 \(2^k\) ！那么对于 \(pq=2X\)，\(p,q\) 函数值相同，且必然有一个位于一类，一个位于二类，那么两类个数相等。
接下来可以用线段树 / 数组维护