[CF1463B] Find The Array

考虑构造出一种情况 bi,bi+1b_i,b_{i+1} 之间的约束条件永真，一个自然的想法是令 bib_i 为 22 的幂。

既然是 22 的幂次，那就让每一个绝对值里的值尽可能小，所以这里找 kk 使得 2k≤ai<2k+12^k \le a_i<2^{k+1}。

此时 2∑∣ai−bi∣=∑(2ai−2k+1)<∑ai=S2\sum |a_i-b_i|=\sum(2a_i-2^{k+1})<\sum a_i=S。

题解给出了另一种方法，既然想让这个约束条件永真，只要相邻两个元素有一个 11 也能满足这一点，自然另一个就填对应的 aia_i。

然后，2∑i=odd(ai−1)+2∑i=even(ai−1)=2S−2n2\sum_{i=\texttt{odd}}(a_i-1)+2\sum_{i=\texttt{even}} (a_i-1)=2S-2n，所以一定有一个值 ≤S−n<S\le S-n<S。

AC Code。

[CF1366D] Two Divisors

首先，(d1,d2)∣d1+d2(d_1,d_2)\mid d_1+d_2，所以 (d1,d2)=1(d_1,d_2)=1 是 (d1+d2,ai)=1(d_1+d_2,a_i)=1 成立的必要条件。

进一步地，从算术基本定理的角度考虑，把 aia_i 分解后变成 p1k1p2k2…pmkmp_1^{k_1}p_2^{k_2}\dots p_m^{k_m}。

显然 m=1m=1 时，任意一个非 11 的因子 dd 都满足 p1∣dp_1\mid d，不可能找到 d1,d2d_1,d_2 满足 d1⊥d2d_1\perp d_2。

当 m≥2m\ge 2 时，我们需要找到 d1,d2d_1,d_2 满足 d1⊥d2d_1\perp d_2 并且 ∀1≤j≤m,pj∤d1+d2\forall 1\le j\le m, p_j\not\mid d_1+d_2。

当 pj∣d1p_j\mid d_1 时，pj∣d1+d2p_j\mid d_1+d_2 成立当且仅当 pj∣d2p_j\mid d_2，而又因为 d1⊥d2d_1\perp d_2 得知这是不可能的。

因此这就给出了一个构造方法，让每一个 pjp_j 都是 d1d_1 或 d2d_2 的因子即可。

AC Code。