全て \(\max A\) に合わせようとするとうまくいかず、\(\max A\) よりある程度大きい値に揃えようとするとうまく行くようなケースについて考えます。

\(\mu(n)\) をメビウス関数とし、\(\displaystyle M(n)=\sum_{k=1}^n \mu(k)\) とします。

全てを \(T\) に揃えようとした時に \(i\) を選ぶ回数を \(x_i(T)\) 回とします。\(x_i(T) \geq 0\) が必要ですが操作を \(i\) の約数全てに \(x_i(T)\) 足す、と言い換えることで負も許すことにします。

\(\displaystyle T-A_k=\sum_{i\le N, k | i} x_i(T)\) をメビウス変換することで \(\displaystyle x_i(T)=\sum_{k\le N,i|k}\mu\left(\frac ki\right)(T-A_k)\) が得られます。この式の差分を取ることで、\(\displaystyle x_i(T)-x_i(T-1)=M\left(\left\lfloor \frac Ni\right\rfloor\right)\) が得られます。

全ての \(i\) に対して \(x_i(T) \geq 0\) を満たす最小の \(T\) を \(\max A+c\) \((c>0)\) とします。

\(\max A+c-1\) では \(x_i(\max A+c-1)<0\) を満たす \(i\) が存在するということなので、\(\displaystyle M\left(\left\lfloor \frac Ni\right\rfloor\right)>0\) を満たす \(i\) が存在する必要があります。一方、\(n=2,3,\ldots,93\) に対し \(M(n) \le0\) であり、初めて \(M(n)>0\) を満たす \(2\) 以上の \(n\) は \(n=94\) です。したがって、上の嘘解法を撃墜するケースを作成するためには \(N\geq 94\) を満たす必要があります。

次に、\(c\) ができるだけ大きくなるようなケースを考えます。

\(\displaystyle \frac N2 < j \le N\) に対し、\(N\) 以下の \(j\) の倍数は \(j\) のみなので \(x_j(T) = T - A_j \geq c\) です。\(\displaystyle \frac N2 < j \le N\) を満たす \(j\) は \(\displaystyle \left\lceil \frac N2\right\rceil\) 個あるので、\(\displaystyle \sum_i x_i(T)\geq \left\lceil \frac N2\right\rceil c\) が成り立ちます。一方、\(A_1\) を \(T\) に合わせることを考えると \(\displaystyle \sum_i x_i(T)=T-A_1=\max A+c-A_1< 10^9+c\) より、合わせて \(\displaystyle c<\frac{10^9}{\left\lceil \frac N2\right\rceil-1}\) が得られます。\(N\geq 94\) であることを踏まえると \(c \le 21739130\) となり、\(c\) の上界として \(21739130\) が得られます。

そして、この \(c\) の上界は実際に達成可能です。まず、\(N=94\) として \(1\le i\le 47\) に対し \(x_i=0\) 、\(48\le i\le 94\) に対し \(x_i=c\) とし、\(T=47c+1\) とします。ここから \(\displaystyle A_k=T-\sum_{i\le N,k|i} x_i\) を元に \(A\) を作ることで目的のケースを作ることができます。

具体的には次のケースです：

94
1 499999991 673913031 760869551 826086941 847826071 869565201 891304331 913043461 913043461 934782591 934782591 934782591 956521721 956521721 956521721 956521721 956521721 978260851 978260851 978260851 978260851 978260851 978260851 978260851 978260851 978260851 978260851 978260851 978260851 978260851 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981 999999981

他にも \(N\) が \(95\) から \(100\) 、\(146\) から \(148\) などで類似のケースを作ることができます。