注意到 $[1,n]$ 中至多 $\lfloor\frac{n}{2}\rfloor$ 个数有 $2$ 作为因子。
故 $n$ 为偶数时 $ans=2$，否则 $ans=1$。
偶数的话 $2,1,4,3,\dots,n,n-1$ 匹配即可。奇数 $1,2,3,4,\dots,n-1,n$ 匹配即可。
QOJ.ac
QOJ
Discussion #801 for Problem #16489. GCD Maximum
Type: Editorial
Status: Open
Posted by: cyx
Posted at: 2026-01-26 15:57:14
Last updated: 2026-01-26 15:58:01
New Editorial for Problem #16489
Comments
No comments yet.