鲜花：今年又在 luogu 被卡7级线了。
赛时
T1 看见区间操作还以为是贪心+数据结构，然后再看两眼发现这原来是个伪装的多测。
对于每一个元素 \(m\)，相当于要构造一组 \(xA+yB=m\) 的 \((x,y)\) 解，这是扩欧。
单纯是不行的，题目上要使得 \((|x|+|y|)_{min}\)。
但是我忘记了扩欧的通解公式了，所以以下内容是我赛时的手推过程：（肯定不是最简的，只是赛时乱推的）
求出来扩欧的 \((x,y)\) 并判断无解后，先令
\[X'=\frac{xm}{\gcd(A,B)},Y'=\frac{ym}{\gcd(A,B)} \]然后设置两个偏系数 \(a,b\) 使得
\[(X'+a)A+(Y'-b)B=m \]拆项得
\[(X'A+Y'B)+aA-bB=m \]移项得 \(aA=bB\)。
因为有两个变量，不好处理，所以要把它们用同一个变量表示出来。
把原式变成
\[a\frac{A}{\gcd(A,B)}\gcd(A,B)=b\frac{B}{\gcd(A,B)}\gcd(A,B) \]然后同时乘 \(\gcd(A,B)\) 得
\[aA\gcd(A,B)=bB\gcd(A,B) \]从而有
\[\frac{a\gcd(A,B)}{B}=\frac{b\gcd(A,B)}{A} \]于是令 \(\frac{a\gcd(A,B)}{B}=\frac{b\gcd(A,B)}{A}=k\)，得
\[a=\frac{Bk}{\gcd(A,B)},b=\frac{Ak}{\gcd(A,B)} \]推出来这个以后，就可以得到 \(k=x\) 与 \((|x|+|y|)=y\) 的函数关系式为
\[y=|X'+\frac{B}{\gcd(A,B)}x|+|Y'-\frac{A}{\gcd(A,B)}x| \]感性看一眼发现这玩意下凸，所以可以用三分求解（虽然能求零点，但我忘了这个的正确性了，保险起见用了三分）
写了一遍就过了。
标签：aA,2024.11,frac,gcd,NOIP,bB,20,扩欧 From： https://www.cnblogs.com/Lydic/p/18556677