AGC problems
Problem C
AGC038 C - LCMs
如果没有现成的数论函数来完成容斥，可以自己造一个！
let
\[ \frac1n=\sum_{d|n}{f(d)} \]
\[ \begin{aligned} \textrm{lcm}{(x, y)} =&\ \frac{xy}{\gcd(x,y)} \\ =&\ xy\sum_{d|x,y}{f(d)} \end{aligned} \]
\[ \mathrm{ans}(i)=\sum_{d|a_i}f(d)\sum_{j<i}a_j[d\ |\ a_j] \]
AGC040 C - Neither AB nor BA
将奇数位上\(A\rightarrow B\),将不能选\(AB\ BA\)转换成不能选\(AA\ BB\)。
结论：\(A\), \(B\)各不能超过一半。
AGC041 C - Domino Quality
大构造，人工智能。
AGC035 C - Skolem XOR Tree
大构造x2
根据样例提示，有\(\bigoplus_{i=1}^{2^k-1}i=1\)。
对于\(n=2^k\)，只有一个第\(k\)位出现，显然-1.
对于\(n \&1\)，将大于\(2^{\mathrm{31-clz(n)}}-1\)的部分按\((2k,2k+1)\)分组。
对于\(n \& 1=0\)，特判前三个数，其余类似处理。